Maximum Subarray Sum

Given an integer array nums, find the subarray with the largest sum and return the sum of the elements present in that subarray.

A subarray is a contiguous non-empty sequence of elements within an array.

Brute Force#

Try every possible subarray by fixing a start index and extending the end index while accumulating the sum. Update the global maximum whenever the current running sum beats it. While this is straightforward and correct, it checks O(n²) subarrays and leads to a Time Limit Exceeded verdict on large inputs — Kadane's algorithm reduces this to O(n) by making a greedy local decision at each step.

• Check all subarrays

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum=INT_MIN;

        for(int i=0;i<nums.size();i++){
            int sum = 0;
            for(int j=i;j<nums.size();j++){
                sum += nums[j];
                maxSum = max(maxSum, sum);
            }
        }

        return maxSum;
    }
};

Time Complexity: O(n^2) --> TLE

Space Complexity: O(1)

Optimal Solution#

Intuition (Kadane's Algorithm): At every index, we face a binary choice: extend the current subarray or start fresh. If the running sum has gone negative, carrying it forward only drags down whatever comes next — so we discard it and start a new subarray from the current element (reset sum = 0).

We always record the best sum seen before potentially resetting, so even an all-negative array returns the correct single largest element.

Key invariant: sum always represents the maximum subarray sum ending at the current index (after the reset rule). maxSum tracks the global best across all positions.

The reset rule (if sum < 0, sum = 0) is the entire algorithm — everything else is bookkeeping.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        long long maxSum=LLONG_MIN;

        long long sum = 0;
        for(int i=0;i<nums.size();i++){
            sum += nums[i];
            if(sum > maxSum){
                maxSum = sum;
            }
            if(sum<0)
                sum=0;
        }

        return maxSum;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Follow up#

Intuition (Tracking the subarray): Same reset logic as above, but we also track indices. Whenever sum resets to 0, the next element starts a candidate subarray, so we record start = i. Whenever we hit a new maxSum, we lock in ansStart = start and ansEnd = i — these mark the best window found so far.

The start pointer only advances on a reset, so it always points to the beginning of the current live subarray. The answer indices only update when we beat the global max, so they always reflect the window that produced it.

• Print the subarray with max sum

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        long long maxSum=LLONG_MIN;

        long long sum = 0;

        int start = 0, ansStart=-1, ansEnd=-1;
        for(int i=0;i<nums.size();i++){

            if(sum==0)
                start=i;

            sum += nums[i];

            if(sum > maxSum){
                maxSum = sum;
                ansStart = start;
                ansEnd = i;
            }
            if(sum<0){
                sum=0;
            }
        }

        for (int i = ansStart; i <= ansEnd; i++) {
            cout << nums[i] << " ";
        }

        return maxSum;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)