ORIGINAL CODING QUESTION

Best practice momentum

Daily momentum can rise or fall. Find the maximum sum of a nonempty contiguous segment of the daily changes.

Open practice workspace

Original exercise · medium. Editorial role relevance does not imply a company has asked this question.

Input and output

First integer n, then n daily changes. Print the maximum segment sum.

Constraints

1 ≤ n ≤ 10,000; -10,000 ≤ change ≤ 10,000. The segment must be nonempty.

Example 1

Input

6
-2 4 -1 3 -5 2

Output

The segment 4, -1, 3 has sum 6.

Example 2

Input

3
-7 -2 -5

Output

-2

Choose the single value -2.

Explain your approach

Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?

Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.

Hint 1

Track the best segment ending at the current position.

Hint 2

Restart when the new value beats extending the previous segment.

Hint 3

Use end = max(x, end + x), and keep the largest end. Initialize from the first element.

Practice this question

Save your work privately, explain decisions and return to your revision queue.

Open practice workspace Browse the question library →