Maximum Subarray

Lab C++ Advanced 30 points

Read n integers and print the largest sum of a contiguous non-empty subarray (Kadane's algorithm).

Input

Line 1: n. Line 2: n integers.

Output

One integer.

Example

Input

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

Output

Sample input available Sample output available

Editor

C++

Hints

At each position, either extend the previous subarray or start fresh.

Solution explanation

Kadane's algorithm solves this in one O(n) pass.

Show solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> v(n);
    for (auto &x : v) cin >> x;
    long long best = v[0], current = v[0];
    for (int i = 1; i < n; i++) {
        current = max(v[i], current + v[i]);
        best = max(best, current);
    }
    cout << best << "\n";
    return 0;
}

Output

Answer