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.
More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
1.O(n)
amazing的解法
需要记录连续的和和需要丢弃前面重新开始的地方
1
2
3
4
5
6
7
8
9
10
11
12
| public class longestSubstring {
public int maxSubArray(int[] nums) {
if(nums.length==0) return Integer.MIN_VALUE;
int result = nums[0];int temp=nums[0];
for(int i=1;i<nums.length;i++){
temp=Math.max(temp+nums[i], nums[i]);
result=Math.max(result, temp);
}
return result;
}
}
|
2.Divide and conquer approach
What is divide and conquer?
http://blog.csdn.net/xyd0512/article/details/8220506
http://open.163.com/special/opencourse/algorithms.html
事实上分治算法最好味O(nlogn)， 不如线性算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0)
return Integer.MIN_VALUE;
return helper(nums, 0, nums.length - 1);
}
public int helper(int[] nums, int b, int e) {
int middle = (b + e) / 2;
if (b == e)
return nums[b];
int leftmax = helper(nums, b, middle);
int rightmax = helper(nums, middle+1, e);
int temp = 0;
int leftm = nums[middle];
int rightm = nums[middle + 1];
for (int i = middle; i >= b; i
temp += nums[i];
if (temp > leftm)
leftm = temp;
}
temp = 0;
for (int i = middle + 1; i <=e; i++) {
temp += nums[i];
if (temp > rightm)
rightm = temp;
}
return Math.max(Math.max(leftmax, rightmax), leftm + rightm);
}
}
|