53. Maximum Subarray

Kadene’s approach:(O(n))

Get Kunal Debnath’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Kadane’s Algorithm is an efficient O(n) method to find the maximum sum contiguous subarray by discarding negative prefixes.It keeps a running subarray sum and resets it when it becomes negative, while tracking the maximum sum seen.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum=0,maxst=INT_MIN;
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
            if(maxst<sum){
                maxst=sum;
            }
            if(sum<0){
                sum=0;
            }
        }
        return maxst;
    }
};