「转」[解题报告] -(https://blog.csdn.net/feliciafay/article/details/18860997)
动态规划： Kadane's algorithm
题目如下：
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。
max_sum 必然是以A[i](取值范围为A[0] ~ A[n-1])结尾的某段构成的，也就是说max_sum的candidate必然是以A[i]结果的。如果遍历每个candidate，然后进行比较，那么就能找到最大的max_sum了。
假设把A[i]之前的连续段叫做sum。可以很容易想到:
1. 如果sum>=0，就可以和A[i]拼接在一起构成新的sum'。因为不管A[i]多大，加上一个正数总会更大，这样形成一个新的candidate。
2. 反之，如果sum<0，就没必要和A[I]拼接在一起了。因为不管A[i]多小，加上一个负数总会更小。此时由于题目要求数组连续，所以没法保留原sum，所以只能让sum等于从A[i]开始的新的一段数了，这一段数字形成新的candidate。
3. 如果每次得到新的candidate都和全局的max_sum进行比较，那么必然能找到最大的max sum subarray.
在循环过程中，用max_sum记录历史最大的值。从A[0]到A[n-1]一步一步地进行。
我的代码:
我的代码太弱，还是来看经典代码，上面的分析过程是一个简单的动态规划，这个算法叫做 Kadane's algorithm。时间复杂度显然是O(N)因为数组只被扫描了一遍。
//经典代码Kadane's algorithm O(N)时间复杂度 72ms过大集合
class Solution{
public:
int maxSubArray(int A[], int n) {
int sum=0; //或者初始化为 summ = INT_MIN 也OK。
int max_sum=INT_MIN; //这里一定要赋值max_sum=INT_MIN否则遇到全部为负数的数组将出错。
for(int i=0;i<n;i++){
if(sum>=0){
sum+=A[i];
}else{
sum=A[i];
}
if(sum>max_sum){
max_sum=sum;
}
}
return max_sum;
}
};
小结：
(1)动态规划的特点子问题和原问题有相似的结构 (smaller and overlapping subproblem)
(2)如果这道题目要求返回最大sum子数组的起始下标和结束下标呢？稍微改改就OK。
//返回MaxSubArray的起始下标和结束下标
class Solution{
public:
vector<int> maxSubArray(int A[], int n) {
int sum=0;
int max_sum=INT_MIN;
int start=0;
int end=0;
vector<int> res_index;
for(int i=0;i<n;i++){
if(sum>=0){
sum+=A[i];
}else{
sum=A[i];
start=i;
}
if(sum>max_sum){
max_sum=sum;
end=i;
}
}
res_index.push_back(start);
res_index.push_back(end);
return res_index;
}
};
update 2014-10-09:
重新理解一下本题: 假设从数组下标a到数组下标b这段是找到的maximum subarray.如何证明a~b就是最大的这段呢?
首先，a之前的数一定是不是正数，否则可以把a~b更新为(a-1) ~ b。这说明a~b的起点一定是个正数。
然后，假设a和b之间有个下标c，则必然有 a~ c > 0，否则可以扔掉a~c直接从c+1开始找。这说明可以记录从a开始到当前数的和，如果这个和是负数就舍去，否则就不停地计算并且得到当前的最大值。
class Solution {
public:
int maxSubArray(int A[], int n) {
int max_sum = INT_MIN;
int sum = INT_MIN;
for (int i = 0; i < n; ++i) {
if (sum < 0) sum = 0;
sum += A[i];
if (sum > max_sum)
max_sum = sum;
}
return max_sum;
}
};
