Java program Algorytm

0

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

0
  1. Dodaj kontrolnie wypisywanie znalezionego ciągu
        if(listaRos2.size() > listaMa2.size()){
            System.out.println(listaRos2.size() + " " + sumaRos2);
            System.out.println(listaRos2);
        }

analogicznie w pozostałych przypadkach.
2. Nie rozumiem tego fragmentu

        if(listaRos2.size() == listaMa2.size()){
          if(sumaMa2 >= sumaRos2){
            System.out.println(listaMa2.size() + " " + sumaMa2);
          }
          if(sumaMa2 < sumaRos2){
                System.out.println(listaRos2.size() + " " + sumaRos2);
          }
        }

nie masz się kierować sumą, tylko położeniem znalezionego podciągu:

        if(listaRos2.size() == listaMa2.size()){
          if(sumaMa2.get(0)<=sumaRos2.get(0)){
            System.out.println(listaMa2.size() + " " + sumaMa2);
          }
          if(sumaMa2.get(0)>=sumaRos2.get(0)){
                System.out.println(listaRos2.size() + " " + sumaRos2);
          }
        }
0

Zmienilem algorytm na taki ale nadal wystepuja bledy wiecie moze jak go zooptymalizowac ??
Problem polega na tym ze przyklady dzialaja natomiast jak wrzucam na platforme spox to nie przechodzi pozytywnie testów.

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>();
				
	     long suma = 0;
	     int indexMa;
	     int indexRos;
	     int indexMa2;
	     int indexRos2;
		
		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));
		
		indexMa=0;
		indexRos=0;
		indexMa2=0;
		indexRos2=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);
			}else{
				listaMa.removeAll(listaMa);
				listaMa.add(liczba);
				indexMa = i;
			}
			if(listaMa.size() > listaMa2.size()){
				listaMa2.removeAll(listaMa2);
				listaMa2.addAll(listaMa);
				indexMa2 = indexMa;
			}
		//Rosnący	
			
			if(liczba >= listaRos.get(listaRos.size()-1)){
				listaRos.add(liczba);
			}else{
				listaRos.removeAll(listaRos);
				listaRos.add(liczba);
				indexRos = i;
			}
			if(listaRos.size() > listaRos2.size()){
				listaRos2.removeAll(listaRos2);
				listaRos2.addAll(listaRos);
				indexRos2 = indexRos;
			}
		
		}
		if(listaRos2.size() > listaMa2.size()){
			for(int j=0;j<listaRos2.size();j++){
				suma +=listaRos2.get(j);
			}
		System.out.println(listaRos2.size() + " " + suma);
		}else if(listaRos2.size() < listaMa2.size()){
			for(int j=0;j<listaMa2.size();j++){
				suma +=listaMa2.get(j);
			}
		System.out.println(listaMa2.size() + " " + suma);
		}else{
			if(indexMa2 < indexRos2){
			for(int j=0;j<listaMa2.size();j++){
				suma +=listaMa2.get(j);
				}
			System.out.println(listaMa2.size() + " " + suma);
			}else{
			for(int j=0;j<listaRos2.size();j++){
				suma += listaRos2.get(j);
			 }
			System.out.println(listaRos2.size() + " " + suma);
			}
		}
	}
}

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