Cod sursa(job #825111)

Utilizator DreptateeDreptate Alexandru I. Dreptatee Data 27 noiembrie 2012 15:00:37
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
// Cea mai lunga subsecventa de suma maxima.
// Complexitate: O(N)
#include <fstream>
using namespace std;
#define INF 0x3f3f3f3f

ifstream is("1.in");
ofstream os("1.out");

int a[1002];
int n;

int main()
{
    int k, j;
    is >> n >> k;
    for ( int i = 0; i < n; i++)
        is >> a[i];

    int s =  0;       // suma secventei curente
    int Smax = -INF;
    int St, Dr;
    int p1 = 0, p2 = 0;  // pozitiile stanga si dreapta a capetelor secventei curente
    for ( int i = 0; i < n; i++)
    {
		s += a[i];
		if ( s >= 0 )
        {
			p2 = i;

			for( int i = p1; i < p2; ++i )
                ++j;
            if ( s > Smax && j >= k )
            {
                for ( int i = p1; i <= p2; ++i )
                        ++k;
                Smax = s;
				St = p1, Dr = p2;
			}
		}
		else
		{
		    j = 0;
			s = 0;
			p1 = i + 1;
        }
    }


    os << St+1 << '\n';
    os << Dr+1 << '\n';
    if ( Smax != -INF )
		os << Smax << '\n';

    is.close();
    os.close();
    return 0;
}