Try   HackMD

53. Maximum Subarray

leetcode網址

問題

找出一個子陣列,且此子陣列的數值總和是最大的,回傳這個最大值

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
        The subarray [4,-1,2,1] has the largest sum 6.

Idea

又是一題Kadane's algorithm,這次是keep一個sum和一個最大值maxi

  • sum: 不斷的累加數值,如果小於0,就變成0重新開始累加數值
  • maxi: 再迭代陣列過程中更新目前最大值

Solution

時間複雜=O(N);空間複雜度=O(1)

int maxSubArray(vector<int>& nums) {
    int maxi= INT_MIN, sum=0;

    for(auto&num: nums){
        sum+=num;
        maxi = max(maxi, sum);
        if(sum<0)sum=0;
    }

    return maxi;
}