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.
简要解析：
本道题主要考查最大连续子序列和的求解方式。
我们可以这样考虑：当我们从头到尾遍历这个数组的时候，对于数组里的一个整数，它有两种选择：1. 加入之前的SubArray；2. 自己另起一个 SubArray。
考虑到有这两种情况，如果之前SubArray的总体和大于0，则认为其对后续结果有益，选择加入之前的SubArray
如果之前SubArray的总体和为0或者小于0，则认为其对后续结果无益，甚至是有害（小于0时），这种情况下选择以这个数字开始，另起一个 SubArray。
设状态为f[j]，表示以 S[j] 结尾的最大连续子序列和，则状态转移方程如下：
f[j] = max{f[j ?1] + S[j],S[j]}, 其中1 ≤ j ≤ n
target = max{f[j]}, 其中1 ≤ j ≤ n
n 情况一：S[j] 不独立，与前面的某些数组成一个连续子序列，则最大连续子序列和为 f[j ?1] + S[j]。
n 情况二：S[j] 独立划分成为一段，即连续子序列仅包含一个数 S[j]，则最大连续子序列和为 S[j]。
实现代码：
// LeetcodeTest.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <climits>
#include <ctime>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstdlib>
#include <windows.h>
#include <string>
#include <cstring>
using namespace std;
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int result = nums[0], count=0;
for(int i=0; i<n; i++){
count +=nums[i];
result = max(result,count);
if(count<0)
count=0;
}
return result;
}
};
int main(){
vector<int>nums;
for(int i=0; i<6; i++){
nums.push_back(i);
}
Solution s;
cout<<s.maxSubArray(nums)<<endl;
system("pause");
return 0;
}
【leetcode】Maximum Subarray (53)
原文：http://www.cnblogs.com/dragonir/p/6189194.html