• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Spoj - Stefan

VPS Starter Arubacloud
0 głosów
253 wizyt
pytanie zadane 19 stycznia 2017 w C i C++ przez 10kw10 Pasjonat (22,880 p.)

Jak przyspieszyc ten algorytm, a dokladniej petle ?

Link do zadania http://pl.spoj.com/problems/FZI_STEF/

Komunikat: Przekroczono limit czasu

#include <iostream>
#include <vector>
int main()
{
    int t,*m,suma=0;
    std::cin>>t;
    m=new int [t];
    std::vector <int>kasa;
    for(int i=0; i<t; i++)std::cin>>m[i];
    for(int k=t;k>0;k--)
    {
        for(int i=0; i<k; i++)
        {
            suma=0;
            for(int j=i; j<k; j++)suma+=m[j];
            kasa.push_back(suma);
        }
    }
    int maks=kasa[0];
    for(int i=1; i<kasa.size(); i++)if(kasa[i]>maks)maks=kasa[i];
    if(maks<0)std::cout<<0;
    else std::cout<<maks;
    kasa.clear();
    delete[] m;
    return 0;
}

 

1 odpowiedź

0 głosów
odpowiedź 19 stycznia 2017 przez jeremus Maniak (59,720 p.)
wybrane 19 stycznia 2017 przez 10kw10
 
Najlepsza

zanim klikniesz w ten link , pokombinuj trochę.

Algorytm , który zastosowałeś to brutal force.

Pewnie działa , ale jest czasochłonny.

Jak już nic nie wymyślisz to zerknij tutaj: albo poszukaj informacji na temat : maksymalna suma podciągu liczb

http://namiekko.pl/tag/podciag-o-najwiekszej-sumie/

 

komentarz 19 stycznia 2017 przez 10kw10 Pasjonat (22,880 p.)

Kocham spoja

Komunikat: Bledna odpowiedz

Testowalem juz rozne wejscia, nawet te z forum spoja i wyniki sa dobre.

kod:

#include <iostream>
#include <algorithm>
int main()
{
    int t,*m,maks,suma;
    std::cin>>t;
    m=new int [t];
    for(int i=0;i<t;i++)std::cin>>m[i];
    suma=maks=m[0];
    for(int i=1;i<t;i++)
    {
        maks=std::max(m[i],maks+m[i]);
        suma=std::max(suma,maks);
    }
    if(suma<0)std::cout<<0;
    else std::cout<<suma;
    delete[] m;
    return 0;
}

 

Podobne pytania

0 głosów
1 odpowiedź 230 wizyt
pytanie zadane 21 marca 2020 w SPOJ przez Sashimo Użytkownik (740 p.)
0 głosów
1 odpowiedź 422 wizyt
pytanie zadane 22 grudnia 2019 w C i C++ przez Teslum_369 Gaduła (4,190 p.)
0 głosów
1 odpowiedź 483 wizyt
pytanie zadane 5 kwietnia 2019 w C i C++ przez Niedzwiadekk Nowicjusz (140 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...