提示
LintCode中的相关算法题实现代码，可以在我的GitHub中下载。
题目需求
描述
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
样例
给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
挑战
要求时间复杂度为O(n)
解题思路
利用动态规划，我们这里使用一个数组保存每一个阶段的和。这里主要的步骤是：
1.如果一个元素大于这个元素和前面的和，那么就保存这个元素，否者保存这个元素和前面的和的和。
解决动态规划的主要思路是找出初始状态和转化方程式，这里的主要转化方程式是
f(x)=max{a[i],a[I]+b[i-1]},这里b数组表示下标I-1的和。
实现代码
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> &nums) {
// write your code here
if(nums.size()==0) return 0;
vector<int> tmp;
tmp.push_back(nums[0]);
for(int i=1;i<nums.size();i++)
{
if(nums[i]+tmp[i-1]>nums[i])
{
tmp.push_back(nums[i]+tmp[i-1]);
}
else
{
tmp.push_back(nums[i]);
}
}
int sum=tmp[0];
for(int i=1;i<tmp.size();i++)
{
if(tmp[i]>sum)
{
sum=tmp[i];
}
}
return sum;
}
};
