首页 > 代码库 > Maximum Subarray <LeetCode>

Maximum Subarray <LeetCode>

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.

 

 

算法:用动态规划进行求解,时间复杂度是O(n

 1 class Solution { 2 public: 3     int maxSubArray(int A[], int n) { 4         if(n==1)  return A[0]; 5         int b; 6         int max=INT_MIN; 7         b=A[0]; 8         if(b>max)  max=b; 9         for(int i=1;i<n;i++)10         {11             if(b<0) b=A[i];12             else b=b+A[i];13             if(b>max)  max=b;14         }15         return max;16     }17 };

 

)

Maximum Subarray <LeetCode>