C++ подмассив проблема

[Azgor]

приёмы написания эффективных алгоритмов (вместо трёх и более циклов всего два или один - максимальная сложность алгоритма указана в условии, О(х)), все размерности всех одномерных массивов 100000:
-в массиве целых чисел найти непрерывный подмассив, сумма элементов которого максимальная; вывести два индекса (начало, конец) и получившуюся сумму ( O(n) )

#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <iomanip.h>
using namespace std;
const int max_kl=100000;

int main()
{
    int n,l=0,r,ts=0,ms=0,temp;
    int mas[max_kl];
    bool b1=0;
    srand((unsigned)time(NULL));
    cout << "Vvedite razmernost' massiva -> ";cin>>n;cout <<endl;
    for(int i=0;i<n;i++)
    {
            /*cout << "Wwedite " << i+1 << "-element: " << endl;
            cin >> mas[i];*/
            mas[i]=rand()%(99+99)-99;
            cout << setw(5)<< mas[i];
    }
    cout <<endl;
    ts=mas[0];
    temp=1;
    for(int i=1;i<n;i++)
    {
      if(mas[i]>0){b1=1;break;}
      if(mas[i]>ts){ts=mas[i];temp=i+1;}
    }
    if(b1==1)
      {
             for(int i=1;i<n;i++)
             {
                ts=ts+mas[i];
                if(ts<0)
                {
                temp=i;ts=0;
                }
                if(ts>ms)
                {
                ms=ts;r=i;l=temp;
                }
             }
      cout <<"Otvet-> l: "<<l+1<<" r: "<<r+1<<" ms: "<<ms<<endl;
      }
      else cout<<"Otvet-> " << temp <<"  "<< ts<<endl;   
    system("pause");
    return 0;
}

Проблема состиит в том, что если например массив заполнить так -7 5 -9 то программа не работает.... А также есть баги с определением левой границы подмассива. Объясните причину, кому не лень разбираться, и , если можно, методы преодоления этого. Зарание спасибо.

[pproger]

-в массиве целых чисел найти непрерывный подмассив, сумма элементов которого максимальная; вывести два индекса (начало, конец) и получившуюся сумму ( O(n) )

что значит непрерывный подмассив? элементы которого упорядочены по возрастанию или по убыванию? или не содержащий нуля? твой код тяжело парсить, поэтому объясни

[Azgor]

Непрерывается подмассив. Например - есть массив из 10 елементов 1 -21 3 -40 5- 15 7 0 25 0. Подмассив с наибольшей суммой будет с a[i]=6 по a[i]= 9. И не важно есть 0 или нет. Без сортировки. Простой гсч. Так понятней?

[pproger]

ну вот. идея не моя, немного пофиксил алгоритм, что то такое получилось

#include "stdio.h"
#include "stdlib.h"
#include "time.h"

#define SIZE 100

int main()
{
	int mass[SIZE];
	int i = 0, j = 0, s = 0;
	int i_best = 0, j_best = 0, s_best = 0;

	srand((unsigned)time(0));

	for (i = 0; i < SIZE; i++)
		mass[i] = (rand() % 100) * (rand() % 2 == 0 ? 1 : -1);

	for (i = 0; i < SIZE; i++)
		printf("%d ", mass[i]);
	
	for (j = 0, i = 0; j < SIZE; j++) {
		if (mass[j] < 0) {
			if (s_best < s) {
				i_best = i;
				j_best = j - 1;
				s_best = s;
			}
			if ((s += mass[j]) <= 0) {
				i = j + 1;
				s = 0;
			}
		} else {
			s += mass[j];
		}
	}
	
	if (s_best < s) {
		i_best = i;
		j_best = j - 1;
		s_best = s;
	}

	printf("\n\n");
	printf("start = %d\nstop = %d\nsum = %d\n", i_best, j_best, s_best);
	printf("\n\n");

	for (i = i_best; i <= j_best; i++)
		printf("%d ", mass[i]);

	printf("\n\n");

	return 0;
}

как раз O(n)

[Azgor]

Хм, идея интересная... Ну не скромничай немного пофиксил... Код настолько прост, что с 1 прогляда видишь суть и алгоритм... И вопрос - что это с гсч ты натворил? Первый раз такое вижу честно говоря... И могу только предположить, каким образом он заполняет...

[pproger]

И вопрос - что это с гсч ты натворил? Первый раз такое вижу честно говоря... И могу только предположить, каким образом он заполняет...

mass[i] = (rand() % 100) * (rand() % 2 == 0 ? 1 : -1);

rand генерит число, берем от него остаток от деления на 100, получаем число от 0 до 99, умножаем на остаток от деления на 2 нового генерированного числа (результат 0 или 1), возвращаем 1 либо -1. вторая часть ранда нужна, чтобы подмешать в массив отрицательные числа