05 August 2008
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
给一个数组，找到一个子数组，子数组的元素加起来的和最大，并返回这个和。这道题用O(n)的办法就是从左扫到右，将临时的tempSum初始化为Integer.MIN_VALUE，当遇到一个元素时，判断这个元素和之前sum的大小，如果加入当前元素更大，就改变tempSum的值；如果当前元素的值更大，之前的tempSum也不用保留了，一直到末尾。
这道题也可以用DP中的Kadane’s Algorithm来进行优化；既然是DP，首先解决子问题的公式(即状态方程)，如果想象子问题是这样的公式：maxSubArray(int nums[], int i, int j)，代表从i位置到j位置是最大的maxSubArray，那么我们的目标就是要分解maxSubArray(nums, 0, nums.length - 1)成子问题，但再往下确是没办法再分了；所以需要换一种思维，把子问题的公式当作maxSubArray(int nums[], int i)，表示从位置0到位置i的maxSubArray：
maxSubArray(nums, i) = maxSubArray(nums, i - 1) > 0 ? maxSubArray(nums, i - 1) : 0 + nums[i];
DP擅长优化指数级别的算法为多项式的复杂度，对于本身已是多项式则优化不明显，Time：O(n)；Space：O(1)。
O(n)顺序从左扫描到右的做法
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
long prevSum = 0, result = Integer.MIN_VALUE; // result得为最小值而不是0，因为preSum可能为负数
for (int num : nums) {
prevSum = Math.max(num, prevSum + num);//因为只用知道最大的sum是多少就行了，不用知道subarray的起始和终止位置，对于当前的元素来说，只有加入计算或者不加入计算两个选择，如果当前元素num加上之前的prevSum的和比当前的num还要小的话，之前的prevSum就可以舍弃掉了，反之则保留。
result = Math.max(result, prevSum);//比较已有的result和新得到的sum看谁大
}
return (int)result;
}
}
另外一种做法，如果nums[i]是负数，那么它不可能代表最优序列的起点，因为任何包含nums[i]的作为起点的子序列都可以通过使用nums[i+1]作为起点得到改进（少加nums[i]这一个负数，所以sum肯定更大）。类似的，任何负的子序列也不可能是最优子序列的前缀（原理相同），联机算法，复杂度一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxSubArray(int[] nums) {
int max_so_far = nums[0]; //目前为止的最大值，初始化为第一个元素，[-1,-2,-3,-4]这样的全负数子序列就可以考虑在内了
int max_ending_here = 0;//以当前数为终点的子序列的最大值
for(int i = 0; i < nums.length; i++) {
max_ending_here = max_ending_here + nums[i];
if(max_so_far < max_ending_here) {
max_so_far = max_ending_here;
}
if(max_ending_here < 0) {//当前元素为重点的子序列的sum小于0的时候，下一个元素重新开始(反正前面都是负的了，不要了)
max_ending_here = 0;
}
}
return max_so_far;
}
}
DP的做法，其实上面的做法也是DP优化空间后的做法，下面是DP原生用数组来存储中间状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
long[] dp = new long[len]; //dp[i]就是以num[i]结尾的最大子序列
dp[0] = nums[0];
long result = dp[0]; // 一个元素的情况
for (int i = 1; i < len; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
result = Math.max(result, dp[i]);
}
return (int)result;
}
}