Maximum Size Subarray

twitter oa 题，如果都是positive value，则用two pointer 扫窗口久行了。但是该题目是可能含有negtive value， brutle force 做法是直接第一遍求出和，然后第二遍俩俩扫求最大。

element书上给一一种o（n)的做法,,

就是两个array，一个是prefixsum，另外一个存的是当前元素i的右边包括i的prefixsum最小值。因为一但以i结束大于k了，那么再移动i也没有任何意义了

这个题让我想到了yahoo的另外一道面经题，就是一个array，求arr[i] 小于arr［j]的 j－ i的最大间隔。

public static int find(List<Integer> A, int k){

  List<Integer> prefixSum = new ArrayList<Integer>();
  int sum = 0;
  for(int a : A){
    sum += a;
    prefixSum.add(sum);
  }

  if(prefixSum.get(prefixSum.size() - 1) <= k){
    return A.size();
  }

  List<String> minPrefixSum = new ArrayList<>(prefixSum);
  for(int i = minPreFixSum.size() - 2; i>=0; i--){
    minPreFixSum.set(i, Math.min(minPrefixSum.get(i), minPrefixSum.get(i + 1)));

  }

  int start = 0;
  int end = 0;
  int max = 0;

  while(start < A.size() && end < A.size()){
    int minCurSum = a > 0? minPrefixSum.get(b) - minPrefixSum.get( a - 1): minPrefixSum.get(b);
    if(minCurrSum <= k){
      max = Math.max(max, b - a + 1);
    }
    b++;
    }else{
      a++;
    }
}
  return max;

  }