Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*Na tablicy napisane są dwa ciągi zer i jedynek.
- Chcemy teraz w każdym z tych ciągów skreślić niektóre cyfry tak,
- żeby pozostałe ciągi były takie same oraz były uporządkowane,
- tj. po pierwszym wystąpieniu jedynki nie mooże już wystąpić
- żadne zero (czyli np. 0000111111). Jaki najdłuższy ciąg może
- pozostać na tablicy?
- Na wejściu podane są długości obu ciągów oraz same ciągi np:
- 4 4
- 0 1 0 1
- 0 0 1 1
- daje wynik:
- 3
- [ bo taki sam ciąg to : 0 1 1 i powstaje on z pierwszego
- poprzez skreślenie ostatniego 0 oraz z drugiego poprzez
- skreślenie pierwszego zera]
- inny przykład:
- 5 5
- 0 1 0 1 1
- 0 1 1 0 0
- daje wynik:
- 3
- [ ciąg: 0 1 1]
- }*/
- import java.util.*;
- public class lab02 {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- System.out.println("Podaj dlugosci 1. ciagu znakow");
- int size1 = in.nextInt();
- System.out.println("Podaj 1. ciag znakow o dlugosci: " + size1 + " skladajacy sie z 0 lub 1");
- int[] chain1 = new int[size1];
- for (int it = 0; it < size1; it++) {
- int temp = in.nextInt();
- if ((temp == 0) || (temp == 1))
- chain1[it] = temp;
- }
- System.out.println("Podaj dlugosci 2. ciagu znakow");
- int size2 = in.nextInt();
- System.out.println("Podaj 2. ciag znakow o dlugosci: " + size2 + " skladajacy sie z 0 lub 1");
- int[] chain2 = new int[size2];
- for (int it = 0; it < size2; it++) {
- int temp = in.nextInt();
- if ((temp == 0) || (temp == 1))
- chain2[it] = temp;
- }
- // MAX CIAG Z 1. //
- ArrayList chain1Zero = new ArrayList(); // maximum 0 i dopełnienie 1
- ArrayList chain1One = new ArrayList(); // maximum 1 i dopełnienie 0
- int i = 0;
- int j = size1 - 1;
- int lastIndex = 0;
- while (i < size1 - 1) { // maximum 0 z pierwszego ciagu
- if (chain1[i] == 0) {
- chain1Zero.add(chain1[i]);
- lastIndex = i;
- i++;
- } else {
- i++;
- }
- }
- i = lastIndex;
- while (i < size1 - 1) { // maximum 0 dopelniamy 1
- if (chain1[i] == 1) {
- chain1Zero.add(chain1[i]);
- lastIndex = i;
- i++;
- } else {
- i++;
- }
- }
- lastIndex = 0;
- while (j > 0) {
- if (chain1[j] == 1) { // maximum 1 z pierwszego ciagu
- chain1One.add(chain1[j]);
- lastIndex = j;
- j--;
- } else {
- j--;
- }
- }
- j = lastIndex;
- while (j > 0) {
- if (chain1[j] == 1) { // maximum 1 dopelniam 0
- chain1One.add(chain1[j]);
- lastIndex = j;
- j--;
- } else {
- j--;
- }
- }
- int maxSize1 = chain1One.size() > chain1Zero.size() ? chain1One.size() : chain1Zero.size();
- // MAX CIAG Z 2. //
- ArrayList chain2Zero = new ArrayList();
- ArrayList chain2One = new ArrayList();
- i = 0;
- j = size2 - 1;
- lastIndex = 0;
- while (i < size2 - 1) { // maximum 0 z druiego ciagu
- if (chain2[i] == 0) {
- chain2Zero.add(chain2[i]);
- lastIndex = i;
- i++;
- } else {
- i++;
- }
- }
- i = lastIndex;
- while (i < size2 - 1) { // maximum 0 dopelniamy 1
- if (chain2[i] == 1) {
- chain2Zero.add(chain2[i]);
- lastIndex = i;
- i++;
- } else {
- i++;
- }
- }
- lastIndex = 0;
- while (j > 0) {
- if (chain2[j] == 1) { // maximum 1 z pierwszego ciagu
- chain2One.add(chain2[j]);
- lastIndex = j;
- j--;
- } else {
- j--;
- }
- }
- j = lastIndex;
- while (j > 0) {
- if (chain2[j] == 1) { // maximum 1 dopelniam 0
- chain2One.add(chain2[j]);
- lastIndex = j;
- j--;
- } else {
- j--;
- }
- }
- int maxSize2 = chain1One.size() > chain1Zero.size() ? chain1One.size() : chain1Zero.size();
- int maxSize = maxSize1 < maxSize2 ? maxSize1 : maxSize2;
- System.out.println("\n\nMax. dlugosc podciagu niemalejacego: " + maxSize + "\n\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement