Maximum Subarray I II III

Leave a comment

August 21, 2016 by oneOokay

Maximum Subarray I:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.


Kadane’s algorithm专门用来解决这个问题: 求一个数组中的一个subarray使得它有最大的max sum. O(n)

一个Array A,长度为n.

Sum[i]表示:在array A的0-i个元素中,以元素A[i]结尾的subarray的max sum的值

那么Sum[i+1]的值为Sum[i]+A[i+1]如果Sum[i]>0;或为A[i+1]如果Sum[i]<0.

Best Time to Buy and Sell Stocks I


Maximum Subarray II:

与Best Time to buy and sell stock II ( only 2 transactions allowed) 是类似的。

两个数组扫描两次:第一次从左到右left[]: 从0至i的max subarray value; 第二次从右到左扫描right[]:从i至end的max subarray value.最后for loop一次,left 与 right相加,取最大值返回。

public int maxTwoSubArrays(ArrayList nums) {
// write your code
if (nums == null || nums.size() <= 1) {
return 0;
}

int len = nums.size();
int[] left = new int[len];
int[] right = new int[len];

//scan twice
//first scan: from left to right: left[i]: 0 – i: max subarray sum
int sum = 0;
int minSum = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i ++) {
sum += nums.get(i);
max = Math.max(sum – minSum, max); //这一步不能直接left[i] = , 因为max的会发生变化,需要用于下一次的计算。所以最后将max的值赋给left[i]
minSum = Math.min(minSum, sum);
left[i] = max;
}

//second scan: from right to left: right[i]: i – end: max subarray sum
sum = 0;
minSum = 0;
max = Integer.MIN_VALUE;
for (int i = len – 1; i >= 0; i –) {
sum += nums.get(i);
max = Math.max(max, sum – minSum);
minSum = Math.min(minSum, sum);
right[i] = max;
}

max = Integer.MIN_VALUE;
for (int i = 0; i < len – 1; i ++) {
max = Math.max(max, left[i] + right[i + 1]); //题目:non-overlapping subarrays
}
return max;
}

Maximum Subarray III:

必然是dp无疑了。 三种解法:九章的local与global 和 max解法以及这里的prefixSum: http://blog.csdn.net/nicaishibiantai/article/details/44585383

这里有个对global & local解法的解释:http://hehejun.blogspot.com/2015/01/lintcodemaximum-subarray-iii.html

以后细读吧。。。

终于全部刷完了所有的Arrays & Numbers 的题 =。=

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: