najlepsze sumy

0

Najlepszą sumą ciągu liczb a1, a2, …, an nazywamy największą wartość wśród sum złożonych
z sąsiednich elementów tego ciągu. Na przykład dla ciągu: 1, 2, -5, 7 mamy następujące sumy:
1
1+2 = 3
1+2+(-5) = -2
1+2+(-5)+7 = 5
2
2+(-5) = -3
2+(-5)+7 = 4
-5
-5+7 = 2
7
Zatem najlepszą sumą jest 7 (zwróć uwagę, że jeden element też uznajemy za sumę).
Zaproponuj algorytm wyznaczania najlepszej sumy dla dowolnego ciągu liczb całkowitych. Na jego
podstawie napisz program do obliczenia najlepszych sum ciągów liczb.
Wejście
W jednej linii znajduje się ciąg liczb całkowitych zakończony liczbą 0. Liczb jest nie więcej niż 500000,
ich wartość mieści się w przedziale [-1000, 1000].
Wyjście
Największa suma złożona z kolejnych elementów ciągu.
Przykład
Dla danych wejściowych: poprawną odpowiedzią jest:
1 2 -5 7 7
............................................................................................................................................................................................
Czy mógłby mi ktoś pomóc i powiedzieć, czemu mój program nie działa? Wyniki wychodzą niby dobre. Jestem początkująca, więc będą to z pewnością głupie błędy, i nie jestem pewna czy się gdzieś nie pogubiłam.

#include <iostream>
using namespace std;
int n,k, t[10000], suma=0, maxi, suma1, maxx;
int main ()
{
    cin>>n;

    for(int i=0; i<n; i++)
    {
        cin>>k;
        maxi=k;
        suma=suma+k;
        t[i]=suma;
        if(suma>maxi)
        maxi=suma;
        else
        maxi=maxi;  
    }
    for(int i=0; i<n; i++)
    {
        suma1=t[n-1]-t[i];
        maxx=t[n-1];
        if(suma1>maxx)
        maxx=suma1;
        else
        maxx=maxx;  
    }
    if(maxx>maxi)
    maxi=maxx;
    cout<<maxi;
    return 0;
}
0

Na temat tytułu, suma zawsze jest najlepsza kiedy większa D
Formatowanie kodu: http://forum.4programmers.net/998482
if nie musi mieć else zwłaszcza nic nie działającego
http://forum.4programmers.net/1101404

0
#include <iostream>
#include <vector>
int main() {
  int max = 0;
  size_t tabSize;
  std::cin >> tabSize;
  std::vector<int> numbers(tabSize);
  for (int i = 0; i < tabSize; ++i) {
    std::cin >> numbers[i];
  }
  for (int j = 0; j < tabSize; ++j) {
    int tempMax = 0;
    for (int k = j; k < tabSize; ++k) {
      tempMax += numbers[k];
      if (tempMax > max) max = tempMax;
    }
  }
  std::cout << max << "\n";
}

Dość proste, ale na pewno nienajlepsze rozwiązanie(np. nie jest idiotoodporne).

EDIT: Też ważne jest do jakiego przedziału należą wyrazy tego ciągu.

1

kod który napisałem dla zadania "stefan" na spoj (https://pl.spoj.com/problems/FZI_STEF/), więc zmienne mają niepasujące do tego nazwy ale przechodzi w O(n) o ile użytkownik nie poda samych ujemnych liczb. No chyba że możemy nie brać żadnej, wtedy pokaże poprawą sumę czyli 0

#include <iostream>

using namespace std;

int main()
{
    long long ilekoncertow,maxzysk=0,zysk=0;
    cin >> ilekoncertow;
    //cout << "Zaplanowano " << ilekoncertow << " koncertów " << endl;
    for (int i=0;i<ilekoncertow;i++)
    {
        int liczba;
        cin >> liczba;
        zysk=zysk+liczba;
        if (zysk>maxzysk) maxzysk=zysk;
        //cout << "dodano " << liczba <<  " i aktualny zysk to " << zysk << endl;
        if (zysk<0) zysk=0;
    }
     cout << maxzysk << endl;

    return 0;
}
0
#include <iostream>

using namespace std;

int main()
{
    long long ilekoncertow, maxzysk = -1, zysk = 0;
    int najwyzsza = INT_MIN;
    bool dodatnia = false;
    cin >> ilekoncertow;
    //cout << "Zaplanowano " << ilekoncertow << " koncertów " << endl;
    for (int i = 0; i < ilekoncertow; ++i)
    {
        int liczba;
        cin >> liczba;
        zysk = zysk + liczba;
        if (zysk > maxzysk) 
        {
            maxzysk = zysk;
            dodatnia = true;
        }
        //cout << "dodano " << liczba <<  " i aktualny zysk to " << zysk << endl;
        if (zysk < 0) 
        {
            zysk = 0;
            if (!dodatnia && najwyzsza < liczba) najwyzsza = liczba;
        }
    }
    if (maxzysk == -1) maxzysk = najwyzsza;
    cout << maxzysk << endl;

    return 0;
}

Dodałem obsługę samych minusów, nie zwiększając dużo złożoności obliczeniowej. Jednak jest późno i polecam sprawdzić ten kod. Dodałem tylko jedno przypisanie i to zmiennej logicznej i jednego ifa który będzie wywoływał się tylko gdy maxzysk spadnie poniżej 0 i po pierwszej liczbie dodatniej będzie szybko ubijany.

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