首页 > 代码库 > Maximum Subarray 连续子数组最大和

Maximum Subarray 连续子数组最大和

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.

此题为经典的求连续子数组最大和问题,除了暴力的解法,想办法用O(n)时间来做。

直接贴代码:

 1 class Solution { 2 public: 3     int maxSubArray(int A[], int n) { 4         if(A == NULL || n < 1) 5             return -1; 6              7         int max = A[0]; 8         int temp = 0; 9         10         for(int i = 0 ; i < n ; i++){11             if(temp < 0)12                 temp = A[i];13             else14                 temp += A[i];15                 16             if(temp > max)17                 max = temp;18         }19         20         return max;21         22     }23 };

 

Maximum Subarray 连续子数组最大和