剑指30：动态规划之最大连续子序列之和
连续子数组的最大和
http://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
动态规划解法原理及C++语言实现（附暴力枚举法）：
///////////////////////////////////////////////
①动态规划：
首先把问题转换为“截止(包含)当前元素的最大子序列之和”，即拆分为array.size()个子问题；然后用动态规划求解每个子问题，建立当前问题和前一个问题的关系即可；
首先解决第一个问题：dp[0]=array[0];
当前问题和前一个问题的关系如下：
dp[n-1]>0时：dp[n]=array[i]+dp[n-1]；
dp[n-1]<0时：dp[n]=array[i]；
最后找出动态规划数组dp中的最大元素即可。
///////////////////////////////////////////////
class Solution {
public://动态规划解法，只遍历一遍数组
int FindGreatestSumOfSubArray(vector<int> array) {
int dp[array.size()];//也可以用单独一个数记录
dp[0] = array[0];
int max = array[0];
for(int i = 1;i < array.size();i++){
int newmax = array[i] + dp[i-1];
if(newmax > array[i])
dp[i] = newmax;
else
dp[i] = array[i];
if(dp[i] > max)
max = dp[i];
}
return max;
}
}; ///////////////////////////////////////////////
②暴力枚举+排序
///////////////////////////////////////////////
class Solution {
public://暴力枚举+排序
int FindGreatestSumOfSubArray(vector<int> array) {
vector<int> res;
for(int i = 0;i < array.size();i++){
int temp = array[i];
res.push_back(temp);
for(int j = i+1;j < array.size();j++){
temp += array[j];
res.push_back(temp);
}
}
sort(res.begin(),res.end());
return res[res.size()-1];
}
};
