/*
  A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

  Write a function:
  
  class Solution { public int solution(int[] A); }

  that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

  For example, given array A such that:

  A[0] = 3  A[1] = 2  A[2] = -6
  A[3] = 4  A[4] = 0
  the function should return 5 because:

  (3, 4) is a slice of A that has sum 4,
  (2, 2) is a slice of A that has sum −6,
  (0, 1) is a slice of A that has sum 5,
  no other slice of A has sum greater than (0, 1).
  Write an efficient algorithm for the following assumptions:

  N is an integer within the range [1..1,000,000];
  each element of array A is an integer within the range [−1,000,000..1,000,000];
  the result will be an integer within the range [−2,147,483,648..2,147,483,647].
 */

#include <bits/stdc++.h>
using namespace std;

ostream& operator<<(ostream& os, const pair<int,int>& p)
{
    return os << "(" << p.first << "," << p.second << ")";
}

void printVPair(vector<pair<int,int>>& v) { for (auto i: v) { cout << i << " "; } cout << endl; }

template <typename Container> void printC(Container& c)
{ for (auto i: c) { cout << i << " "; } cout << endl; };

class Solution
{
public:
    int solution(vector<int>& A)
    {
        int local_max = 0;
        int maxSum = INT_MIN;
        // Kadanes's algorithm, local_max at index i is the max of
        // A[i] and the sum of A[i] and local_max at index i-1

        // Wikipedia: if the array contains all non-positive numbers,
        // then a solution is any subarray of size 1 containing the
        // maximal value of the array (or the empty subarray, if it is
        // permitted).
        
        for (size_t i = 0; i < A.size(); i++)
        {
            local_max = max(A.at(i), A.at(i) + local_max);
            if (local_max > maxSum)
                maxSum = local_max;
        }

        return maxSum;
    }
};

int main(void)
{
    vector<tuple<vector<int>,int>> testCases = {
        // { {3,2,-6,4,0}, 5 },
        // { {-2,1,-3,4,-1,2,1,-5,4}, 6 },
        // { {-4,-3,-2,-1}, -1 },
        { {1,2,3,4,5}, 15},
    };

    for (auto tc: testCases)
    {
        Solution s;
        vector<int>& input = get<0>(tc);
        int expected = get<1>(tc);
        int result = s.solution(input);
        
        int width = 10;
        cout << setw(width) << "input: "; printC(input);
        cout << setw(width) << "result: " << result << endl;        
        cout << setw(width) << "expected: " << expected << endl;        
        cout << (result == expected ? "\033[32mpassed\033[0m" : "\033[31mfailed\033[0m") << endl;        
        cout << "----------------------------\n";
    }
}