Kadane

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

using namespace std;

int n, v[1000], aux, MAX, END, length[1000];

int main()
{
    srand(time(NULL));

    cout << "Find the subarray with the biggest sum in a given array.\n";
    cin >> n;
    for( int i=1 ; i<=n ; i++)
    {
        v[i] = rand() % 21 - 10;
        cout << v[i] << " ";
    }
    aux = v[1];
    length[1] = 1;
    MAX = aux;
    END = 1;
    for( int i=2 ; i<=n ; i++ )
    {
        if( v[i] > aux + v[i] )
        {
            aux = v[i];
            length[i] = 1;
        }
        else
        {
            aux = aux + v[i];
            length[i] = length[i-1] + 1;
        }

        if( aux > MAX )
        {
            MAX = aux;
            END = i;
        }
    }

    cout << "\nSum: " << MAX << "\nStarts at: " << END-length[END]+1 << " Ends at: " << END ;
    return 0;
}