Practice here

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Brute Force#

The straightforward idea is to enumerate every possible subarray and compute its sum, then track the maximum. For each starting index i, extend the subarray to every ending index j >= i while maintaining a running sum. This is exhaustive and correct but checks O(n²) subarrays unnecessarily.

• Find all possible subarray sums -> Pick maximum.

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(sum, maxSum);
            }
        }
        return maxSum;
    }
};

Time Complexity: O(n²) --> TLE

Space Complexity: O(1)

Better Approach: Kadane's Algo#

Kadane’s Algorithm is an efficient method to find the maximum sum of a contiguous subarray in a given array.

• The idea is to keep adding elements to a running sum.
• If at any point the sum becomes negative, discard it by resetting to 0.
• Keep updating the maximum sum seen so far.

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

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

Time Complexity: O(n)

Space Complexity: O(1)

Summary#