C++UCS301
Complexity Lab C++ Setup Visualizer
Practice arena
C++17·2 s·128 MB
LinearFoundation

Best contiguous sum

Find the maximum sum of a non-empty contiguous subarray. The array may contain only negative values, so an empty subarray is not allowed.

Input

  • — The first line contains T.
  • — Each case contains n followed by n signed integers.

Output

Print one maximum contiguous sum per case.

Technique

Kadane's algorithm

Target

O(n) time · O(1) extra

Constraints & sample
  • 1 ≤ n ≤ 200,000
  • The sum of n is at most 300,000
  • Use a 64-bit integer for the sum

Sample input

3
6
-2 1 -3 4 -1 2
4
-8 -3 -6 -2
5
1 2 3 4 5

Expected output

5
-2
15
Review the concept

Before you submit

  • Test the smallest valid input and one awkward edge case.
  • Keep the solution within O(n) time · O(1) extra.
  • Match spacing and line breaks exactly before checking 8 hidden cases.
main.cpp
Draft saved locally · 483 / 30,000
Ln 1, Col 1Spaces: 4UTF-8LFC++17

Visible testcases

Editable and stored only in this browser. Hidden judge cases never change.

Checking your session…

Run checks Sample · Submit checks 8 hidden cases

Run the sample first, then send your solution through 8 hidden cases.

Code runs in an isolated Judge0 environment. Drafts and custom visible cases stay on this device; submission metadata and progress sync to MongoDB.