Wątek przeniesiony 2015-03-06 20:10 z C/C++ przez Shalom.

Maksymalna wartość podtablicy. Algorytm O(n)

0

Witam :)
Mam pewien problem z napisaniem programu o złożonowości O(n) obliczającego maksymalną podtablicę(początek,koniec i max. wartość podtablicy). Program powinien wyglądać tak, że w konsoli użytkownik na wejście podaje: -w pierwszej linii liczba testów , - następnie podaje ilość liczb, które będzie wpisywał(czyli wielkość tablicy, która będzie badana), - w kolejnych n liniach podaje n liczb(całkowitych), będących elementami tablicy). - wartości bezwzględne elementów tablicy <2000. Na wyjściu dla każdego testu program wypisuje wiersz postaci: początek, koniec i maksymalna wartość podtablicy.
Info wyjaśniające o co chodzi dokładniej z tą podtablicą: Dana jest tablica liczb całkowitych a[0],...,a[n-1], n>1. Maksymalną podtablicą nazywamy fragment ciągły a[i],...,a[j] o maksymalnej nieujemnej sumie elementów obliczanej wg. wzoru : suma(i,j)=3*(suma dodatnich el. podtablic)+2*(suma ujemnych el. podtablicy).Jeśli wszystkie liczby są ujemne to podtablica jest pusta.
Sam etap wpisywania tych wszystkich liczb(test,n,liczby do tablicy) nie jest dla mnie problemem, schody pojawiają się jednak przy napisaniu algorytmu do obliczenia tej podtablicy :/
Oto co jedynie udalo mi się zapisać:

#include <iostream>
using namespace std;
int main ()
{
	int i,n,k,t;
	do
	{
		cin>>t;   //wprowadzam liczbe testow
	}while(t<=0);
	
	do {
		cin>>n;   //wprowadzam liczb elementow
	}while(n<1 || n>100000);

	int *tb=new int [n]; 
	for(i=0; i<n; i++)
	{
		cin>>tb[i];
		
	}
	//Co dalej ? 
	
	
	
	return 0;
}

Jestem dopiero początkującym w programowaniu, dlatego za ewentualną infantylność mojego problemu z góry przepraszam. Za wszelką pomoc w napisaniu programu wielkie dzięki! :)

0

W zasadzie tablica jest ci zbędna, sumujesz wprowadzane elementy wg zasad z zadania, na początek 1 będzie początkiem. I teraz jeśli "suma" wychodzi mniejsza od zera, to ustawiasz sumę na zero "początek" na pierwszy dodatni element na który natrafisz. Cały czas naturalnie pamiętasz największą sumę, początek i koniec który z tego uzyskałeś, w przypadku gdyby aktualnie obliczona byłą większa (a wczytana liczba ujemna), modyfikujesz zmienne "wynikowe"

0

Mógłbyś mi to wytłumaczyć trochę prościej, bo nie za bardzo rozumiem, jak to przedstawić w programie :/

1 użytkowników online, w tym zalogowanych: 0, gości: 1