算法题求教（小马、寒武纪的笔试题）

第二题滑动窗口吧

今天小马的第三题，要用单调栈，楼主可以去学习下。

第二题依次遍历每个数，每个数往左找到比他小的那个数为止，往右找到比他小的那个数为止，这个区间就是以当前值作为最小值的时候的结果，遍历一遍取最大。没试过，感觉可以

第一题有点想法，不知对错，遍历a，每个数如果能放第一组也能放第二组，就先跳过，如果只能放第一组或第二组，就放该组并从a中删除该数，并且把他放进该组所需要的那个数也从a里面删除(如果这个数有多个就删除第一个就行)，如果有一个数也不能放第一组也不能放第二组，那就返回-1，这样最后如果有一个组是空的，那就从a里剩下的元素里取一个放到那个空组里就算完成分组了。

今天小马的第三题：dp 以及 deque 都可以做；我贴一下今天dp的垃圾code吧 if __name__ == '__main__':     s1 = input().split(' ')     N, K = int(s1[0]), int(s1[1])     s2 = input().split(' ')     As = [int(s) for s in s2]     dp_sum = [0] * N     dp_max = [0] * N     dp_min = [0] * N     dp_sum[K-1] = sum(As[:K])     dp_min[K-1] = min(As[:K])     dp_max[K-1] = max(As[:K])     ans = (dp_sum[K-1] - dp_min[K-1] - dp_max[K-1]) / (K-2)     for i in range(K, N):         dp_sum[i] = dp_sum[i-1] - As[i-K] + As[i]         if As[i] >= dp_max[i-1]:             dp_max[i] = As[i]         else:             if As[i] >= As[i-K]:                 dp_max[i] = dp_max[i-1]             else:                 if As[i-K] < dp_max[i-1]:                     dp_max[i] = dp_max[i-1]                 else:                     dp_max[i] = max(As[i-K+1: i+1])         if As[i] <= dp_min[i-1]:             dp_min[i] = As[i]         else:             if As[i] <= As[i-K]:                 dp_min[i] = dp_min[i-1]             else:                 if As[i-K] > dp_min[i-1]:                     dp_min[i] = dp_min[i-1]                 else:                     dp_min[i] = min(As[i-K+1: i+1])         v = (dp_sum[i] - dp_min[i] - dp_max[i]) / (K-2)         ans = max(ans, v)     print(ans)

腾讯遮体是否可以这样，因为不能排序，所以数据其实没有规律，直接dp感觉是没法做到的，只能采用for循环，但是可以优化，程序还有优化空间，但是不想优化了 import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class findSubsegmentMax { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); String str = sc.nextLine(); String[] str_1 = str.split(" "); List<Integer> list = new ArrayList<Integer>(); for(int i=0; i<str_1.length; i++) { list.add(Integer.parseInt(str_1[i])); } int n = list.size(), maxNum=0; System.out.println("n: " + n); int[] res; for(int i=0; i<list.size(); i++) { while(i < n) { res = find(list, i, n); if(maxNum < res[0]) maxNum = res[0]; n = res[1] - 1; } n = list.size(); } System.out.println(maxNum); } public static int[] find(List<Integer> list, int m, int n) { Integer min=list.get(m), sum=0, index=-1; for(int i=m; i<n; i++) { if(min > list.get(i)) { min = list.get(i); index = i; } sum += list.get(i); } sum *= min; // System.out.println("sum and index: " + sum + " " + index); int[] ret = {sum, index}; return ret; } }

第一题，每个数顶多有两个链接，也就是说只可能是一条链，或者一个环，环的话只要是偶数个就能搞定，链的话从链头开始分配，如果剩下最后一个那就再特殊判断一下