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. */
PRZYKŁAD 2
wejście:
1 1 7 3 2 0 0 4 5 5 6 2 1
wyjście:
6 20
PRZYKŁAD 3
wejście:
65 87 47 5 12 74 25 32 78 44 40 77 85 4 29 57 55 79 31 63 84 66 62 41 52 36 82 86 6 98 63 65 14 57 75 14 74 15 41 88 27 75 6 78 98 78 22 77 68 74 92 47 30 44 40 52 70 66 17 60 47 97 34 37 23 69 56 57 3 45 7 76 18 35 24 73 47 77 1 84 92 54 18 98 84 36 66 71 92 13 77 28 75 24 46 67 4 63 82 1
wyjście:
4 253
moj kod wyglada tak:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
class Monoto {
public static void main(String[] args){
ArrayList<Integer> listaRos = new ArrayList<Integer>();
ArrayList<Integer> listaMa = new ArrayList<Integer>();
ArrayList<Integer> listaRos2 = new ArrayList<Integer>();
ArrayList<Integer> listaMa2 = new ArrayList<Integer>();
ArrayList<Integer> lista = new ArrayList<Integer>();
int sumaRos = 0;
int sumaRos2 = 0;
int sumaMa = 0;
int sumaMa2 = 0;
String input;
try {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
input = bufferedReader.readLine();
Pattern pattern = Pattern.compile("[0-9]+");
Matcher matcher = pattern.matcher(input);
while(matcher.find()){
lista.add(Integer.parseInt(matcher.group()));
}
bufferedReader.close();
} catch (IOException e) {
e.printStackTrace();
}
listaMa.add(lista.get(0));
listaRos.add(lista.get(0));
listaMa2.add(lista.get(0));
listaRos2.add(lista.get(0));
sumaMa2 = lista.get(0);
sumaMa = lista.get(0);
sumaRos2 = lista.get(0);
sumaRos = lista.get(0);
for(int i=1;i<lista.size();i++){
int liczba = lista.get(i);
//Malejący
if(liczba <= listaMa.get(listaMa.size()-1)){
listaMa.add(liczba);
sumaMa += liczba;
}else{
listaMa.removeAll(listaMa);
listaMa.add(liczba);
sumaMa = liczba;
}
if(listaMa.size() > listaMa2.size() || (listaMa.size() == listaMa2.size() && sumaMa > sumaMa2 )){
listaMa2.removeAll(listaMa2);
listaMa2.addAll(listaMa);
sumaMa2 = sumaMa;
}
//Rosnący
if(liczba >= listaRos.get(listaRos.size()-1)){
listaRos.add(liczba);
sumaRos += liczba;
}else{
listaRos.removeAll(listaRos);
listaRos.add(liczba);
sumaRos = liczba;
}
if(listaRos.size() > listaRos2.size() || (listaRos.size() == listaRos2.size() && sumaRos > sumaRos2 )){
listaRos2.removeAll(listaRos2);
listaRos2.addAll(listaRos);
sumaRos2 = sumaRos;
}
}
if(listaRos2.size() > listaMa2.size()){
System.out.println(listaRos2.size() + " " + sumaRos2);
}
if(listaRos2.size() < listaMa2.size()){
System.out.println(listaMa2.size() + " " + sumaMa2);
}
if(listaRos2.size() == listaMa2.size()){
if(sumaMa2 >= sumaRos2){
System.out.println(listaMa2.size() + " " + sumaMa2);
}
if(sumaMa2 < sumaRos2){
System.out.println(listaRos2.size() + " " + sumaRos2);
}
}
}
}
1 problem jest taki ze ten program jest zly a ja nie za bardzo wiem czemu
2 gdy rozwazamy ostatni przypadek program podaje mi wynik (4 265) a w przykladzie podaje 4 253
Mam prośbe o mała pomoc bo nie za bardzo wiem gdzie są błedy
