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.
又是一題Kadane's algorithm,這次是keep一個sum和一個最大值maxi
sum
maxi
時間複雜=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; }
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up