/* Вводится массив. Найти в нем подпоследовательность из подряд идущих
элементов с наибольшей суммой. */
/* http://forum.vingrad.ru/topic-39011.html, Dov */

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

int main(void)
{
    int ar[]   = {5, 5, 8, -2, -9, 14, -8, 3, 3, 3};
    int sum    = 0;
    int max    = 0;
    int iBeg   = 0;
    int iEnd   = 0;
    int iFirst = 0;
    int i;

    for(i = 0; i < SIZE; i++)
    {
        sum += ar[i];
        if(sum <= 0)
        {
            sum    = 0;
            iFirst = i + 1;
        }
        else if(sum > max)
        {
            max  = sum;
            iBeg = iFirst;
            iEnd = i;
        }
    }

    printf("Index :");
    for(i = 0; i < SIZE; i++)
        printf("%4d", i);

    printf("\nArray :");
    for(i = 0; i < SIZE; i++)
        printf("%4d", ar[i]);

    printf("\nMySeq :");
    for(i = 0; i <= iEnd; i++)
        i < iBeg ? printf("%4d") : printf("%4d", ar[i]);

    printf("\n\nMaxSum: %d\nIndBeg: %d\nIndEnd: %d\n", max, iBeg, iEnd);

    system("pause");
    return 0;
}