Maximum subarray (Kadane's algorithm).

Problem. Find the contiguous subarray with the largest sum and return that sum. For [-2,1,-3,4,-1,2,1,-5,4] the answer is 6 (the subarray [4,-1,2,1]). At least one element exists, and it may be negative.

Brute force — O(n²) time

Try every start, extend to every end, track the max running sum:

int maxSubBrute(int[] a) {
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < a.length; i++) {
        int sum = 0;
        for (int j = i; j < a.length; j++) {
            sum += a[j];
            best = Math.max(best, sum);
        }
    }
    return best;
}

O(n²) — fine for small inputs, too slow at scale.

Optimal — Kadane's algorithm, O(n) time, O(1) space

The insight is a one-line DP. Let cur be the best subarray sum ending exactly at index i. At each element you face a binary choice: extend the previous best subarray, or start fresh at the current element. You start fresh precisely when the running sum has gone negative — a negative prefix can only drag down whatever follows:

public int maxSubArray(int[] a) {
    int cur = a[0];      // best sum ending at current index
    int best = a[0];     // best sum seen anywhere
    for (int i = 1; i < a.length; i++) {
        cur = Math.max(a[i], cur + a[i]);   // start fresh vs extend
        best = Math.max(best, cur);
    }
    return best;
}

cur = max(a[i], cur + a[i]) is the whole algorithm: if cur + a[i] < a[i] then cur was negative and dragging us down, so drop it and restart at a[i]. We track best separately so a strong subarray isn't lost when a later negative tail shrinks cur. One pass → O(n) time, O(1) space.

To also return the indices, track a tentative start that resets whenever you "start fresh," and commit [start, i] whenever cur beats best.