https://leetcode.com/problems/maximum-subarray/description/

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.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解法一

• 动态规划。设f[i]表示第j处，以a[i]结尾的子序列的最大和。注意：f[i]并不是前i-1个数中最大的连续子序列之和，而只是包含a[i]的最大连续子序列的和。我们求出f[i]中的最大值，即为所求的最大连续子序列的和。
• 状态转移方程：f[i] = max{ a[i], f[i - 1] + a[i] }, target = max { f[i] }。
• max - C++ Reference
  • http://www.cplusplus.com/reference/algorithm/max/?kw=max

1 // 2 //  main.cpp 3 //  LeetCode 4 // 5 //  Created by Hao on 2017/3/16. 6 //  Copyright © 2017年 Hao. All rights reserved. 7 // 8  9 #include 
      
       10 #include 
       
        11 using namespace std;12 13 class Solution {14 public:15     int maxSubArray(vector
        
         & nums) {16         // empty array17         if (nums.empty()) return 0;18         19         int result = nums.at(0), f = 0;20         21         for (auto i = 0; i < nums.size(); i ++) {22             // f[i] = max{ a[i], f[i - 1] + a[i] }23             f = max(f + nums.at(i), nums.at(i));24 25             // target = max { f[i] }26             result = max(result, f);27         }28         29         return result;30     }31 };32 33 int main ()34 {35     Solution testSolution;36     37     vector< vector
         
           > vecTest{ {-2, 5, 3, -6, 4, -8, 6}, {}, {
    1, 2, 3, 4, 5} };38     39     for (auto v : vecTest)40         cout << testSolution.maxSubArray(v) << endl;41     42     return 0;43 }
         
        
       
      

解法二

• 分治法，O(nlog(n))。分成两段分别求最大连续子序列的和，再归并。选定中间节点middle，则最大连续子序列和为max { 左边最大连续子序列和，右边最大连续子序列和，包含中间节点的最大连续子序列和 }。计算包含中间节点的最大连续子序列和，则是以中间节点向两边扩张，得到最大前缀+中间节点+最大后缀。

1 // 2 //  main.cpp 3 //  LeetCode 4 // 5 //  Created by Hao on 2017/3/16. 6 //  Copyright © 2017年 Hao. All rights reserved. 7 // 8  9 #include 
      
       10 #include 
       
        11 using namespace std;12 13 class Solution {14 public:15     int maxSubArray(vector
        
         & nums) {16         // empty array17         if (nums.empty()) return 0;18         19         int result = maxSubArrayHelpFunc(nums, 0, nums.size() - 1);20         21         return result;22     }23     24 private:25     int maxSubArrayHelpFunc(vector
         
          & nums, int left, int right) {26         // 叶子结点27         if (left == right) return nums.at(left);28         29         int middle = (left + right) / 2; // 中间节点30         int leftMax = maxSubArrayHelpFunc(nums, left, middle); // 左边最大连续子序列和31         int rightMax = maxSubArrayHelpFunc(nums, middle + 1, right); // 右边最大连续子序列和32         int preMax = nums.at(middle); // 包含中间节点的左边最大连续子序列和33         int sufMax = nums.at(middle + 1); // 包含中间节点的右边最大连续子序列和34         35         // 中间节点向左扩张36         int temp = 0;37         for (auto i = middle; i >= left; i --) {38             temp += nums.at(i);39             if (temp > preMax) preMax = temp;40         }41         42         // 中间节点向右扩张43         temp = 0;44         for (auto i = middle + 1; i <= right; i ++) {45             temp += nums.at(i);46             if (temp > sufMax) sufMax = temp;47         }48         49         // max { 左边最大连续子序列和，右边最大连续子序列和，包含中间节点的最大连续子序列和 }50         return max( max(leftMax, rightMax), preMax + sufMax);51     }52 };53 54 int main ()55 {56     Solution testSolution;57     58     vector< vector
          
            > vecTest{ {-2, 5, 3, -6, 4, -8, 6}, {}, {
    1, 2, 3, 4, 5} };59     60     for (auto v : vecTest)61         cout << testSolution.maxSubArray(v) << endl;62     63     return 0;64 }