DSA sheet / Sorting and searching
Maximum Subarray Sum
Do these first: Repetitions
The problem in brief
Given n integers (n up to 200 000, each between -10^9 and 10^9, possibly negative), print the maximum sum of any non-empty consecutive block of them.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1643.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Trying every start and end is O(n^2) (or worse with naive summing). What information about a block ending at position i is enough to extend it to position i + 1?
-
For a block that must end exactly at position i, there are only two sensible choices: start fresh at i, or extend the best block that ended at i - 1. Which one do you pick and when?
-
If the best block ending just before i has a negative sum, is it worth carrying it along?
-
The answer is the maximum, over all i, of the best block ending at i. Watch the case where every number is negative, and the size of the total.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
This is the canonical “subproblem per end position” idea. Define f(i) = the best sum of a block ending exactly at i. Any such block either is just a[i] or is a block ending at i - 1 extended by a[i], so f(i) = a[i] + max(0, f(i - 1)). That recurrence needs only the previous value, so you keep one running number. The answer is the maximum f(i) seen. This is Kadane’s algorithm, and the reasoning that discards negative prefixes is the whole trick.
There is a second view that connects to prefix sums: a block sum equals P[j] - P[i - 1], so the best block ending at j uses the smallest earlier prefix. Both give O(n).
Common trap: initialising the best answer to 0 is wrong when all numbers are negative, because the block must be non-empty. Start from the first element. The habit: define the state as “best answer that ends here”, write the recurrence, and check the degenerate inputs.
Intuition
Walk along keeping a running total. If the running total ever drops below zero, it is dead weight: you are better off forgetting it and starting from the next element. Keep track of the highest total you ever held.
Approach
- Set cur = a[0] and best = a[0].
- For each next element x: cur = max(x, cur + x); best = max(best, cur).
- Print best.
Pitfalls: sums can reach 2 * 10^5 * 10^9 = 2 * 10^14, so use 64-bit; initialise from the first element so all-negative inputs work; a single element is a valid answer.
Complexity
O(n) time, O(1) memory beyond the input.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long long cur = 0, best = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
cur = (i == 0) ? x : max(x, cur + x);
best = (i == 0) ? x : max(best, cur);
}
cout << best << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
cur = best = int(data[1])
for i in range(2, n + 1):
x = int(data[i])
cur = max(x, cur + x)
if cur > best:
best = cur
print(best)
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
long cur = 0, best = 0;
for (int i = 0; i < n; i++) {
st.nextToken();
long x = (long) st.nval;
cur = (i == 0) ? x : Math.max(x, cur + x);
best = (i == 0) ? x : Math.max(best, cur);
}
System.out.println(best);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
let cur = data[1];
let best = data[1];
for (let i = 2; i <= n; i++) {
cur = Math.max(data[i], cur + data[i]);
if (cur > best) best = cur;
}
console.log(best);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).