Kadane's Algorithm

*/

n = 9

a[] = {4, -8, -2, 8, -1, 3, 2, -6, 2}

Maximum Sub-array are = {8, -1, 3, 2}

Maximum Sub-array Sum = 12

*/

#include<bits/stdc++.h>

using namespace std;

int MaxSum(int a[], int n)

{

    int total = 0, mx = INT_MIN;

    for(int i=0; i<n; i++)

    {

        total = max(a[i], total + a[i]);

        if(mx < total)

            mx = total;

    }

    return mx;

}

int main()

{

    int n;

    cin >> n;

    int a[n];

    for(int i=0; i<n; i++)

        cin >> a[i];

    cout << MaxSum(a, n) << "\n";

    return 0;

}