Професионална програма
Loading...
+ Нов въпрос
LoshoToshi avatar LoshoToshi 16 Точки

Проблем с Max Sequence of Increasing Elements

Здравейте, на задача от Max Sequence of Increasing Elements успях да добутам до 85/100 с това решение: https://pastebin.com/t0tqPPKw .

Условието е :

 Write a program that finds the longest increasing subsequence in an array of integers. The longest increasing subsequence is a portion of the array (subsequence) that is strongly increasing and has the longest possible length. If several such subsequences exist, find the left most of them.

Линк към judge:https://judge.softuni.bg/Contests/Practice/Index/207#6

Моля за помощ къде бъркам, пробвах с отрицателни числа работи, с нулевите тестове работи.

 

 

 

 

Тагове:
0
Fundamentals Module
A.Neshkova avatar A.Neshkova 45 Точки
Best Answer

Разбрах къде е проблемът. Като пробвах кода ти с този вход:   

-2 -1 0 1 0 1 2 3 4 

на конзолата изкарва:  -2 -1 0 1

а изхода трябва да е: 0 1 2 3 4

понеже в проверката проверяваш с  .length()

ако изпринтираш накрая дължината на  maxSequence -  System.out.println(maxSequence.length());

ти изкарва че дължината на ''-2 -1 0 1'' е 9, защото смята спейсовете + минусите + числата,

за това редица с 4 числа излиза, че е по-дълга от редица с 5 числа.

Оправих го като добавих още един counter и в проверката ги сравнявам по counter.

 

Сега дава 100 от 100 в judge. Ето твоя код + добавката:

 

import java.util.Arrays;
import java.util.Scanner;

public class MaxSequenceOfIncreasingElements {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] arr = Arrays.stream(scanner.nextLine()
                .split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int currentCounter = 0;
        int maxCounter = 0;

        String currentSequence = "";
        String maxSequence = "";

        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] < (arr[i + 1])) {
                currentSequence += arr[i] + " ";
                currentCounter++;

                if (maxCounter < currentCounter) {
                    maxCounter++;
                    maxSequence = currentSequence + arr[i + 1];
                }
            } else {
                currentSequence = "";
                currentCounter = 0;
            }
        }

        System.out.println(maxSequence);
    }
}

 

0
LoshoToshi avatar LoshoToshi 16 Точки

Много благодаря за насоката. Tолкова бях зациклил, че явно не съм осъзнал, че сравнявам дължината на стринговете.

1
30/07/2020 09:29:19