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