1.Maximum/Minimum Subarray － 只需要scan一次求出global最大值/最小值。
Maximum Product Subarray – scan一次，需要两个数组记住最大最小值，tricky：最小值＊最小可能是最大。
2.Maximum Subarray II－是上面题目变形。需要scan两次，left／right 各一次。
思考：动态规划中很多时候需要一个local最大值和global最大值。
loop1 是求出包括当前点，也就是local的最大值。
loop2 求出到达当前点的global值，不一定要包括当前。
loop1 and loop2是可以合并写成一个loop的。
public int maxTwoSubArrays(ArrayList<Integer> nums) {
if (nums==null||nums.size()==0){
return 0;
}
int len=nums.size();
int[] left=new int[len];
int[] right=new int[len];
left[0]=nums.get(0);
right[len-1]=nums.get(len-1);
for(int i=1;i<len;i++){ //loop1
left[i]=Math.max(nums.get(i),left[i-1]+nums.get(i));
}
int curMax=left[0];
for(int i=1;i<len;i++){//loop2
int temp=Math.max(left[i],curMax);
left[i]=temp;
curMax=temp;
}
for(int i=len-2;i>=0;i--){
right[i]=Math.max(nums.get(i),right[i+1]+nums.get(i));
}
curMax=right[len-1];
for(int i=len-2;i>=0;i--){
int temp=Math.max(curMax,right[i]);
curMax=temp;
right[i]=curMax;
}
int max=Integer.MIN_VALUE;
for(int i=0;i<len-1;i++){
max=Math.max(left[i]+right[i+1],max);
}
return max;
}
3.Maximum Subarray Difference 需要scan left／right 的最大和最小值
比较差值 Math.max(Math.abs(lMax[i]-rMin[i+1]),Math.abs(lMin[i]-rMax[i+1])
public int maxDiffSubArrays(ArrayList<Integer> nums) {
if (nums.size()==0) return 0;
int len=nums.size();
int[] lMax=new int[len];
int[] lMin=new int[len];
int[] rMax=new int[len];
int[] rMin=new int[len];
int localMin=0;
int localMax=0;
int max=Integer.MIN_VALUE;
int min=Integer.MAX_VALUE;
for(int i=0;i<len;i++){
int temp=nums.get(i);
localMax=Math.max(temp,temp+localMax);
max=Math.max(max,localMax);
lMax[i]=max;
localMin=Math.min(temp,temp+localMin);
min=Math.min(min,localMin);
lMin[i]=min;
}
localMin=0;
localMax=0;
max=Integer.MIN_VALUE;
min=Integer.MAX_VALUE;
for(int i=len-1;i>=0;i--){
int temp=nums.get(i);
localMax=Math.max(temp,temp+localMax);
max=Math.max(max,localMax);
rMax[i]=max;
localMin=Math.min(temp,temp+localMin);
min=Math.min(min,localMin);
rMin[i]=min;
}
max=Integer.MIN_VALUE;
for(int i=0;i<len-1;i++){
int temp=Math.max(Math.abs(lMax[i]-rMin[i+1]),Math.abs(lMin[i]-rMax[i+1]));
max=Math.max(temp,max);
}
return max;
}
4. Maximum Subarray III
dp二维数组
http://www.cnblogs.com/lishiblog/p/4183917.html
5.Minimum Size Subarray Sum( sliding window 做法）
http://techinpad.blogspot.com/2015/05/leetcode-minimum-size-subarray-sum.html
http://blog.csdn.net/nicaishibiantai/article/details/45814397
dev4future 