LEET code -- 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.


跟之前買股票的很像

處理大於0簡單

但是麻煩的是都為負數

原本想要用指標處理

但是 想想乾脆 把全部負數當作特殊例子來處理還比較快

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int maxSubArray(int* nums, int numsSize) { int max=0,sum=0,big=-9999,allnegitive=0; for(int i =0;i<numsSize;i++){ if(nums[i]+sum >=0 ){ sum+=nums[i]; allnegitive=1; }else{ //<0 sum=0; } big= big >nums[i]? big:nums[i]; max = max>sum? max:sum; } return allnegitive==1? max:big; }

------------------
更簡潔一點

1 2 3 4 5 6 7 8 9

int maxSubArray(int* nums, int numsSize) { int max=-999999,sum=0; for(int i =0;i<numsSize;i++){ sum+=nums[i]; max = max>sum? max:sum; if(sum<0)sum=0; } return max; }