https://leetcode.com/problems/maximum-subarray/
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
.
这道题是典型的DP题,转移公式是:
dp[i] = Math.max(A[i], dp[i-1]+A[i])
求出以每个数为结尾,可以得出的最大值,要么是它自己,要么是和前一个数所形成的最大和相加。然后有个全局的max值来保存全局最大的和值。代码如下:
public class Solution {
public int maxSubArray(int[] A) {
int[] dp = new int[A.length];
dp[0]=A[0];
int max = A[0];
for(int i=1; i<A.length; i++){
dp[i] = Math.max(A[i], dp[i-1]+A[i]);
if(dp[i]>max) max = dp[i];
}
return max;
}
}
dp的解法是O(n)的,这道题还有一种解法是divide and conquer,是Introduction to Algorithm里面的例子,思路是maximum subarray要么在左边,要么在右边,要么在中间,那么求出左边最大,右边最大,中间最大,再取最大值,求左边和右边的最大时就按同样的方法递归就行了:
public class Solution {
public int maxSubArray(int[] A) {
return findmax(A, 0, A.length-1);
}
public int findmax(int[] A, int left, int right){
if(left==right) return A[left];
if(left>right) return Integer.MIN_VALUE;
int mid = (left+right)/2;
int lsum = findmax(A, left, mid);
int rsum = findmax(A, mid+1, right);
int csum = maxCrossArray(A, left, right, mid);
return Math.max(Math.max(lsum, rsum), csum);
}
public int maxCrossArray(int[] A, int low, int mid, int high){
int lsum = Integer.MIN_VALUE;
int sum = 0;
for(int i=mid; i>=low; i--){
sum += A[i];
if(sum>lsum){
lsum = sum;
}
}
int rsum = Integer.MIN_VALUE;
sum = 0;
for(int i=mid; i<A.length; i++){
sum+=A[i];
if(sum>rsum){
rsum = sum;
}
}
return Math.max(Math.max(lsum, rsum), (lsum+rsum-A[mid]));
}
}
这个解法的时间复杂度是O(n*lgn),因为每层都需要遍历整个数组求过中间值的最大数组,坑爹的是,leetcode虽然提示说用divide and conquer,结果这个时间复杂度居然过不了大数组。不知道是否真的有O(lgn)的解法。。。。