C++ подмассив

[Azgor]

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

#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 то программа не работает.... Объясните причину, кому не длень разбираться, и , если можно, методы преодоления этого. Зарание спасибо.

 

[Azgor]

Программа написана мною, алгоритм разработался по ходу.
Не всегда одекватно берется левая граница подмассива и вычисляется сумма( пример я привел выше).

И по поводу тегов CODE поподробней, если можно.

 

[DarkKnight]

2Автор: непрерывный подмассив - это что такое? последовательность (1..9...20......)? или все же любя последовательность чисел где каждое последующее является инкр. текущего???

 

[Azgor]

это любая последовательность чисел в массиве(непрырывная) на пример с a[2] po a[9](т.е. берется сумма элементов начиная со 2 и заканчивая 9, причем левая и правая граница последовательности выбирается так, дабы сумма была максимальной.)

 

[DarkKnight]

Все равно смутно понимаю что же нужно сделать.

И алгоритм что по-пьяне особо разобрать не могу....

Но а на твой вопрос ответ

				if(ts>ms)
{
ms=ts;r=i;l=temp;
}

Вот этот код в твоей последовательности не выполниться никогда....
тоесть ms всегда 0
r - не определена вообще
l - тоже ноль

А вообще лично я бы сделал вот так:

	const int N = 4;

int Mass[]={-7,5,-9,4};

int Mass2[N][N];

int Sumatory = -99999999; //Ничтожно малая сумма для определения макс. послед.
int Start,End=0; //Начальный и конечный индекс;
int MaxLen=0; //длина послед. разность нач. индекса и кон. индекса

//Заполняем двумерный массив Mass2[Начало индекс][Конец индекс] = Сумме элементов
for (int i=0;i<N;i++)
{
int Sum = Mass[i];
for (int j=i+1;j<N;j++)
{
Sum += Mass[j];
Mass2[i][j] = Sum;
//cout<<Sum<<endl;
//Ну и сразу же проверим что бы не в пустую (Но массив если что мы сохраняем, так что проверить можем в любой момент программы
if (Sumatory < Mass2[i][j]) //Если работать без дв. массива сюда просто Sum для сравнения!!! Но ИМХО, с дв. массивом красивее смотрится
{
Sumatory = Mass2[i][j]; //Та же история что и с прошлым комментом
Start = i; End = j; MaxLen = j-i; // К Start и к End тут сразу смело можно плюсовать 1, что бы в конце не делать
}

if (Sumatory == Mass2[i][j]) //а вот если они равны, то уже проверяем длину цепочки MaxLen
{
if (MaxLen < j-i) //Ну длина в этом случае, как ты сам понимаешь 1, кстати именно из этой логики я инициализировал j как ты видишь выше
{
Sumatory = Mass2[i][j]; //У кого длинее тот и прав... :-)
Start = i; End = j; MaxLen = j-i;
}
}		
}
}

cout<<Sumatory<<endl<<Start+1<<" "<<End+1<<endl;

 

[Azgor]

l не 0, и r определена и находит верно. А двумерный массив зачем? " одномерных можно же ввести .... Даже короче полуится... Но, все равно - спасибо. Приму к сведенью и такой алгоритм.

 

[Azgor]

Можно проще. Примерно вот так:

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

#define SIZE 3

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]);


s_best=mass[0];
i_best=0;
j_best=0;

for (j = 0, i = 0; j < SIZE; j++)
{
s += mass[j];

if (s<mass[j])
{
s = mass[j];
i=j;
} 

if (s_best < s)
{
i_best = i;
j_best = j;
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");
system("pause");
return 0;
}/*rand генерит число, берем от него остаток от деления на 100,
получаем число от 0 до 99, умножаем на остаток от деления на 2 
нового генерированного числа (результат 0 или 1),
возвращаем 1 либо -1. вторая часть ранда нужна, 
чтобы подмешать в массив отрицательные числа.*/

 

[hosm]

И по поводу тегов CODE поподробней, если можно.

link removed

 

[DarkKnight]

Согласен, алгоритм действительно рабочий, кроме одного НО...
Он может выдавать начало и конец одного и того же индекса(!!!), а один элемент - это не последовательность.....
{2,-3,40,-50,-60} - это контр. пример... по данному алгоритму будет s-2, e-2, sum - 40; а по идеи должно быть s-0,e-2,sum - 39;

Но а свой алгоритм я писал еще на то что бы был учет максимальной последовательности подмассива(по кол-ву элементов)....
А массив двумерный был нужен только для наглядности...