Kadane's Algorithm(Print Sub-Array)

/*

n =

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

Maximum Sum : 12

Maximum Sum Sub-Array : {8, -1, 3, 2}

*/

#include<bits/stdc++.h>

using namespace std;

void maxi(vector<int>a)

{

    int total = 0, mx = INT_MIN;

    int FirstIndx = -1, LastIndx = -1, TempIndx = -1;

    for(int i=0; i<a.size(); i++)

    {

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

        if(a[i] >= total)

            TempIndx = i;

        if(mx < total)

        {

            mx = total;

            FirstIndx = TempIndx;

            LastIndx = i;

        }

    }

    cout << "Maximum Sum :: " << mx << "\n";

    cout << "Sub-array :: ";

    for(int i=FirstIndx; i<=LastIndx; i++)

        cout << a[i] << " ";

}

int main()

{

    int n;

    cin >> n;

    vector<int>a(n);

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

        cin >> a[i];

    maxi(a);

    return 0;

}