Podciąg monotoniczny i spójny

ZADANIE
Rozważmy losowy ciąg liczb naturalnych C. Podaj długość oraz sumę elementów najdłuższego możliwego monotonicznego i spójnego zarazem podciągu ciągu C. W przypadku niejednoznaczności odpowiedzi wskaż pierwszy taki ciąg począwszy od lewej strony.

WEJŚCIE
Wiersz opisujący elementy ciągu C oddzielone znakiem odstępu (kod ASCII 32) zakończony znakiem końca pliku (EOF).

WYJŚCIE
Wiersz zawierający dwie liczby będące rozwiązaniem postawionego problemu oddzielone znakiem odstępu.

OGRANICZENIA
Długość ciągu C dodatnia i ograniczona przez 10^{7, elementy rozważanego ciągu zawarte w przedziale wartości [0,10}9].

LIMITY
Oczekiwana złożoność czasowa rzędu O(n). Oczekiwana złożoność pamięciowa rzędu O(1).

PRZYKŁAD 1
wejście:
8 4 2 3 2
wyjście:
3 14

/* KOMENTARZ DO ROZWIĄZANIA
Poszukiwany podciąg monotonicznie malejący to: 8 4 2.
Długość i suma elementów wskazanego ciągu są równe odpowiednio 3 oraz 14.
*/

#include <cstdio>
#include<conio.h>
using namespace std;

const int MAX = 100000000;
int ilosc, suma, n;
int poczatek, koniec;
int i = 0;
int a[MAX];

int main(){
    
 
    //fscanf(stdin, "%d", &a[0]);
    
    while(i < MAX && scanf("%d", &n)!=EOF){
            scanf("%d", &a[i]);
            i++;
            };
                    
    suma = a[0] + a[1];
    ilosc = 2;
    poczatek = a[0];
    koniec = a[1]; 

To jest fragment mojego kodu. Jakoś, że nie jest dokończony, nie wiem czy działa, pierwszy raz używam scanf i nawet nie wiem czy jest ona w tym przypadku dobrym rozwiązaniem.
Planuję to prostu porównywać potem ifami 3 elementy, środkowy, następny i poprzedni. Jednak nie wiem czy to nie zrobi chaosu nie nie będzie tych ifów za dużo.
Dlatego mam prośbę o wskazówki i uwagi, czy to jak zaczynam jest w ogóle poprawne i jest sens to dokańczać czy może wybrać kompletnie inny sposób, bo ten jest błędny?
Wszystkie wskazówki do dalszego rozwiązania też mile widziane.

to jest proste zadanie.
Zwykłe wyszukiwanie wartości maksymalnej.
Lecisz od początku robisz test czy ciąg jest monotoniczny. Jeśli ciąg przestaje być monotoniczny, testujesz aktualny ciąg jest dłuży od ostatniego znanego ci najdłuższego to go aktualizujesz jego dane. Następnie kontynuujesz poszukiwania.

Wyszło mi coś takiego: (mam zaznaczone, że nierówność nieostra, więc dodaję i przypadek gdy dwie cyfry po sobie są takie same)

                   
    suma = a[0] + a[1];
    dlugi=1;
    najdluzszy=2;
  
    for (int j = 1; j < i-1; j++){
        
        if(a[i+1] >= a[i]){
          dlugi++;
          suma = suma + a[i+1];
          if(dlugi > najdluzszy){
              najdluzszy = dlugi;    
              dlugi=0;   
              } 
        }
              
        if(a[i+1] <= a[i]){
          dlugi++;
          suma = suma + a[i+1];
          if(dlugi > najdluzszy){
            najdluzszy=dlugi;
            dlugi=0;
            }
         }
         
         if(a[i+1] == a[i]){
           dlugi++;
           suma = suma + a[i+1];
           if(dlugi > najdluzszy){
            najdluzszy=dlugi;
            dlugi=0;
            }
         }
    } 

Nie wiem czy dobrze robię z tą sumą, czy może coś się tam poplątało.
Nie wiem czy program działa, skompilował, jednak chyba źle używam funkcji EOF (czy ona jest tu naprawdę konieczna?) bo po wpisaniu jakiś tam liczb i wciśnięciu enter, po prostu przechodzi na drugą linię i czeka na kolejne wpisywanie.

Ktoś by mógł powiedzieć co poprawić czy podać cały kod? Choć pewnie to za wiele nie zmieni, myślę, że albo błąd jest w scanf lub EOF albo źle rozumiem działanie programu i kod ma błędy niżej w pętli :(

1. masz wczytać z pliku

while(i < MAX && scanf("%d", &n)!=EOF){
            scanf("%d", &a[i]);
            i++;
            };

powoduje, że czytasz do tablicy co drygą wartość.
3) pętle masz po indeksie j, natomiast wyszukujesz po indeksie i

A, więc mam sobie utworzyć jakiś plik z tymi danymi a nie pisać je na konsoli? Więc od początku źle na to patrze :/

Może to głupie pytanie, ale pierwszy raz robię zadanie na SPOJ, jeśli dajmy na to zrobię sobie swój plik z danymi, a potem taki kod wrzucę na SPOJa to on sobie utworzy własny plik? Czy uzna to za błąd?

kaczus napisał(a):

while(i < MAX && scanf("%d", &n)!=EOF){
            scanf("%d", &a[i]);
            i++;
            };

powoduje, że czytasz do tablicy co drygą wartość.
3) pętle masz po indeksie j, natomiast wyszukujesz po indeksie i

Chyba już rozumiem czemu co drugą, ale ten kod jest wzorowany na znalezionym w internecie (podobne zadanie) i ktoś właśnie pętlę na tej zasadzie robił.

Więc jeśli czytanie z pliku nie jest zgodne z wymaganiami, to jak ten kod poprawić, by czytał z klawiatury i wpisywał dane dobrze?
Szukam w internecie i co zmienię to wychodzi mi to samo. Nie mogę sobie poradzić z tym znakiem końca linii.

ja bym rozumiał to tak, że ma czytać z pliku, ale ktos tu powyżej twierdzi inaczej - zadań ze SPOJ nie wykonywałem, więc ciężko mi powiedzieć. Dodatkowo zastanowiłbym się, czy tablica tak duża jest w ogóle potrzebna, bo operujesz tylko na elementach i i i+1 (powinno być j i j+1), a z tego co pamiętam, to ktoś się skarżył, że dużej tablicy nie chciało mu przyjąć na SPOJ (zakładając oczywiście, że poprawny jest algorytm, bo nie wnikałem - patrzyłem tylko na ew błędy).

Kwintyl napisał(a):

OGRANICZENIA
Długość ciągu C dodatnia i ograniczona przez 10^{7, elementy rozważanego ciągu zawarte w przedziale wartości [0,10}9].

Wielkość tablicy wzorowana na tym ograniczeniu, więc wydaje mi się, że powinna taka być, choć może źle to rozumiem.

Właśnie przez to, że to SPOJ mam problem, bo gdyby nie on, to w ogóle i zadanie chyba dałoby się rozwiązać inaczej (jak dla mnie prościej) ale jest sporo ograniczeń przez złożoność pamięciową i czasową.

Więc pewnie zadanie jest proste i jak ktoś jest obeznany na SPOJu to szybko zrobi, a ja się męczę i ciągle jest coś nie tak :/

Moja rada trzymaj osobno dane dla ciągów rosnących i malejących. Aktualizacje najdłuższego ciągu rób, gdy ciąg rosnący/malejący się kończy (po czym będzie "restartowany").
Nie pisz wszystkiego w main, funkcje bardzo poprawiają czytelność kodu.

Bo z tego algorytmu co podałeś, to w zasadzie potrzebujesz tablice dwuelementową, jeśli analizę przeprowadzałbyś podczas wczytywania danych. Choć mogę obawiać się, że niestety chyba zły algorytm masz... ale w sumie po przeczytaniu dokładnie o co chodzi w zadaniu - podtrzymuje, że można obyć się bez tablicy wczytywanych elementów - jest zbędna - przynajmniej moim zdaniem.

Możesz też policzyć signum(a[i] - a[i + 1]) dla każdego elementu i wtedy szukać najdłuższego ciągu jednorodnego i jego długość +1 będzie długością najdłuższego podciągu monotonicznego.

W zadaniu nie ma ani słowa o wczytywaniu czegokolwiek z pliku. Natomiast spojowy format zadania pozwala przypuszczać, że wszelkie operacje powinny być wykonywane na wejściu i wyjściu standardowym.

Wielkość tablicy wzorowana na tym ograniczeniu, więc wydaje mi się, że powinna taka być, choć może źle to rozumiem

Chociaż to faktycznie zgodne z wymaganiami (złożoność pamięciowa O(1)), to jest to jednak dość szczególny przypadek, a sama tablica do wykonania tego zadania jest całkowicie zbędna.

while(i < MAX && scanf("%d", &n)!=EOF){
  //scanf("%d", &a[i]);
  // pobrana wartość ze strumienia wejściowego jest w zmiennej n
  a[i] = n;
  i++;
}

można terz prubowac

while(scanf("%d", &a[i++]) != EOF){}

lub

for(int i = 0; scanf("%d", &a[i]) != EOF; ++i){}

ale złorzoność O(1) pokazuje, rze nie nalerzy wczytywać danych do tablicy