Maximum Subarray Sum (Kadane's Algorithm)

Kadane’s algorithm is a one-dimensional DP for a nonempty contiguous subarray with maximum sum. Unlike LIS or LCS, contiguity prevents arbitrary skipping inside the selected range. The state only needs the best sum ending at the current position. We retain start/end indices to output a witness and initialize from the first element so all-negative arrays are handled correctly.

Prerequisites: One-Dimensional DP; contiguous ranges.

Build the idea

1. Recognize the repeated subproblems

   Trying every left/right boundary takes O(n²) sums even with prefix sums. Different candidate subarrays ending at i can be summarized by their maximum sum, because every extension adds the same next value. Constraints up to 200000 favor a constant-work recurrence per position. A subsequence variant would permit skipping negatives and is a different objective.

2. Define the state

   ending is the best sum of a nonempty subarray ending exactly at i. best is the maximum ending value seen anywhere, not just the current suffix. start records the left boundary of ending; left, right record the saved global optimum. These separate meanings prevent returning only a good suffix instead of the best subarray over the entire array.

3. Derive the transition

   A nonempty subarray ending at i either starts at i or extends one ending at i−1. Therefore ending=max(a[i], endingPrevious+a[i]). If the previous ending is negative, start fresh; otherwise extend. When ending strictly improves best, copy the boundaries. Equal sums retain the earlier saved solution; no separate shortest-length tie objective is imposed.

   $$\mathrm{ending}\left[i\right]=\max \left(a\right[i],\mathrm{ending}[i-1]+a[i\left]\right)$$

4. Base cases and computation order

   For n≥1 initialize ending=best=a[0] and all boundaries zero. Process i=1…n−1. This enforces nonempty output even when every value is negative. A version allowing an empty subarray would use a zero option and can return a different answer; the two problems must not be conflated. Output boundaries are converted to 1-based indices.

5. Correctness and invariant

   Induct on i: if a subarray ending at i has more than one entry, its previous portion is bounded by endingPrevious, so the recurrence is an upper bound; starting or appending realizes it. Taking the maximum over endpoint states covers every nonempty subarray exactly by its final index. Only the previous endpoint value is needed, which is why this DP compresses naturally to constant scalar state.

6. Work the example

   For [−2,1,−3,4,−1,2,1,−5,4], the best segment is positions 4…7, values [4,−1,2,1], sum 6. The endpoint states shown below explain the reset at 4 and later decline. For [−5,−2,−7], initializing from data returns −2 rather than an illegal empty sum zero.

   position	1	2	3	4	5	6	7	8	9
   best ending	-2	1	-2	4	3	5	6	1	5

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>a(n);
    for(auto&x:a){
        std::cin>>x;
    }
    long long ending=a[0],best=a[0];
    int start=0,left=0,right=0;
    for(int i=1;i<n;++i){
        if(ending<0){
            ending=a[i];
            start=i;
        }
        else{
            ending+=a[i];
        }
        if(ending>best){
            best=ending;
            left=start;
            right=i;
        }
    } // The optimal subarray is nonempty, even when every value is negative.
    std::cout<<best<<' '<<left+1<<' '<<right+1<<'\n';
}

Complexity analysis

n endpoint states and two alternatives each give O(n) time. The DP itself uses O(1) state; the supplied program stores O(n) input values for clarity. It could stream them. Sum magnitude≤n·10^9 fits long long.

Example input and output

Read n (1..200000), then n integers within ±10^9. Print maximum nonempty subarray sum and its 1-based inclusive left/right boundaries.

Input

9
-2 1 -3 4 -1 2 1 -5 4

Output

6 4 7

For [−2,1,−3,4,−1,2,1,−5,4], the best segment is positions 4…7, values [4,−1,2,1], sum 6. The endpoint states shown below explain the reset at 4 and later decline. For [−5,−2,−7], initializing from data returns −2 rather than an illegal empty sum zero.

Practical applications

Use maximum contiguous gain/loss and as a subroutine in some multidimensional range problems. Prefix-minimum reasoning gives another O(n) formulation. Circular arrays and length constraints require additional reasoning rather than blindly reusing the same state.

Check your understanding

What is the correct answer for [−5,−2,−7] under this contract?

Put it into practice

Check every boundary pair on small random arrays and verify the returned range.