class Solution {public:    int maxSubArray(int A[], int n) {        int cur_sum = 0;        int max_sum = INT_MIN;                for (int i=0; i
     
       max_sum) max_sum = cur_sum;            if (cur_sum < 0) {                cur_sum = 0;            }        }        return max_sum;    }};
     

老题

第二轮：

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(n) = max(f(n-1) + A[0], A[0])

class Solution {public:    int maxSubArray(int A[], int n) {        if (A == NULL || n < 1) {            return INT_MIN;        }        int contsum = A[0];        int maxsum = A[0];                for (int i=1; i

分治法，nlogn, 但是TLE

class Solution {public:int maxSubArray(int A[], int n) {        return dfs(A, 0, n);    }        int dfs(int A[], int start, int end) {        if (start >= end) {            cout<<"range error: start="<
     
      <<", end="<
      
       <
       
         mb ? ma : mb;        int lsum = 0, rsum = 0;        int lmax = INT_MIN, rmax = INT_MIN;                for (int i=mid - 1; i>=0; i--) {            lsum += A[i];            if (lsum > lmax) lmax = lsum;        }                for (int i=mid; i
        
          rmax) rmax = rsum;        }                if (lmax + rmax > maxsum) maxsum = lmax + rmax;        return maxsum;    };};