首页 > 代码库 > 【leetcode】Maximum Subarray

【leetcode】Maximum Subarray

2024-07-07 16:07:22   221人阅读

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.

动态规划经典题，设置一个sum，不停的加A[i],每次跟记录最大值的max比较，如果大于max，就更新max；如果加上某个A[i]，sum变成小于0的数了，就把sum置成0.最后返回max即可。

代码如下：

 1 class Solution {
 2 public:
 3     int maxSubArray(int A[], int n) {
 4         int maxx = -65536;
 5         int sum = 0;
 6         for(int i = 0;i < n;i++){
 7             sum = sum+A[i];
 8             if(maxx < sum)
 9                 maxx = sum;
10             sum = sum >0?sum:0;
11         }
12         return maxx;
13     }
14 };

 

 


联系
我们