Under construction

Still being built. Things may change

Maximum Subarray Sum

Interview

Time limit1sMemory limit128 MB

Summary
Given up to 100,000 integers, compute the maximum sum of a non-empty contiguous subarray.
Level

Easy3 of 10

Topics
Dynamic programming, Array
Solved
No attempts yet

Problem

You are given a sequence of n integers. Find the maximum possible sum obtainable by choosing one or more consecutive elements of the sequence.

Input

The first line contains an integer n (1 ≤ n ≤ 100,000).

The second line contains n integers separated by spaces. Each integer is between -1,000 and 1,000, inclusive.

Output

Print the maximum sum obtainable by choosing one or more consecutive elements.

Examples3

  1. Example 1

    Input
    10
10 -4 3 1 5 6 -35 12 21 -1
    Expected output
    33

  2. Example 2

    Input
    10
2 1 -4 3 4 -4 6 5 -5 1
    Expected output
    14

  3. Example 3

    Input
    5
-1 -2 -3 -4 -5
    Expected output
    -1