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 107, elementy rozważanego ciągu zawarte w przedziale wartości [0,109].
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.