Maximum Subarray — Practice

Problem

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

Examples

Example 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: Subarray [4,-1,2,1] has the largest sum = 6.

Constraints

•1 <= nums.length <= 10^5
•-10^4 <= nums[i] <= 10^4

Hints

Hint 1

The brute force checks every possible subarray's sum directly — O(n^2) if you track a running sum per starting index, O(n^3) if you resum from scratch each time.

Hint 2

At each position, you're really only ever asking one question: is it better to EXTEND the best subarray ending at the previous position, or to START FRESH here? That's Kadane's core insight.

Hint 3

A negative running sum can never help a future subarray — if currentSum drops below the value of the current element alone, discard it and restart from here.

Solutions

public int maxSubArrayBruteForce(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}

Time: O(n^2) · Space: O(1)