LeetCode Maximum Subarray

LeetCode Maximum Subarray

1.题目

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​​.

2.解决方案

class Solution {public: int maxSubArray(int A[], int n) { int sum = A[0] , maxSum = A[0]; for(int i = 1; i < n; i++){ if(sum < 0) sum = 0; //先判断之前的sum能否被这次利用（小于0则抛弃） sum += A[i]; maxSum = max(maxSum, sum); } return maxSum; }};

思路：用一个数来记录之前已经相加的总的值，只要当前加入的值不把它拖累到负数，就留着。

第一个数是-2，直接舍弃。1，可以留着。再-3.总的已经是-2.-3直接舍弃。目前最大值就是1.

然后4，留着。修改最大值为4. -1.可以留着（因为4-1还是大于0）。最大值还是4. 2可以留着。现在最大值是5.1可以留，现在最大值是6. -5可以留，但最大值还是6. 4 可以留，但最大值还是6.

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。