剑指offer——44连续子数组的最大和

 1 class Solution01 {
 2 public:
 3     int FindGreatestSumOfSubArray(vector<int> array) {
 4         if (array.size() == 0)return 0;
 5         int sum = 0, maxS = array[0];
 6         for (int i = 0; i < array.size(); ++i)
 7         {
 8             if (sum < 0)//sum累加和为负的，还不如从我自己加起
 9                 sum = array[i];
10             else
11                 sum += array[i];
12             maxS = maxS > sum ? maxS : sum;
13         }
14         return maxS;
15     }
16 };

 1 class Solution02 {
 2 public:
 3     int FindGreatestSumOfSubArray(vector<int> array) {
 4         if (array.size() == 0)return 0;
 5         vector<int>dp(array.size(), 0);
 6         dp[0] = array[0];
 7         for (int i = 1; i < array.size(); ++i)
 8             dp[i] = max(array[i], array[i] + dp[i - 1]);//加上前面数字的和会不会使和变大
 9         return dp.back();
10     }
11 };