Поиск последовательности в массиве

Задача

Есть массив положительных и отрицательных чисел. Нужно найти последовательность значений, сумма которой будет наибольшая. Например, для массива [-2, 5, -5, 8, -1, 3, 2, 6] наибольшая сумма будет для последовательности [8, -1, 3, 2, 6].

Решение

Пусть нам дан массив:

src_aray = [x1, x2, x3, x4]

Тогда для решения поставленной задачи нужно вычислить и найти наибольшее для следующих последовательностей:

x1+x2+x3
x2+x3
x1
x2+x3+x4
x2+x3
x2
x3+x4
x3
x4

Так как известно, что массив может содержать отрицательные значения, то можно попытаться уменьшить количество вычислений, суммируя только те последовательности, которые начинаются с положительного числа. Только нужно учесть, что массив может полностью состоять из отрицательных чисел.

Тогда алгоритм будет такой:
1. Массив проверяется на наличие положительных чисел.
2. Пошагово проверяем каждый элемент массива xi.
3. Если в массиве нет положительных чисел (худший вариант), вычисляем сумму всех последовательностей, начинающихся с xi.
4. Если в массиве есть положительные числа, вычисляем сумму всех последовательностей, начинающихся с xi, только в случае xi > 0.
5. Среди вычисленных сумм, выбираем наибольшую.

Реализовать этот алгоритм можно так:

// допускаем, что данные всегда передаются валидные
// src_array - исходный массив
// len - его длина
// sindex, eindex - результат поиска - начальный и 
// конечный индексы последовательности
void sub_array(int *src_array, int len, 
                int &sindex, int &eindex)
{
   int sum = src_array[0];
   sindex = 0;
   eindex = 0;
   
   // проверяем наличие положительных значений
   bool has_positive = false;
   for(int i=0;i < len;i++)
      if(src_array[i]>0)
      {
         has_positive = true;
         break;
      }

   for(int i=0;i < len;i++)
   {
      int ssum = src_array[i];
      if(has_positive && ssum < 0) continue;

      for(int j=i;j < len;j++)
      {
         ssum += j>i?src_array[j]:0;
         if(ssum>=sum)
         {
            sum = ssum;
            sindex = i;
            eindex = j;
         }
      }
   }
}