Найти максимальный рейтинг (число) в массиве, где мы не можем пропустить 1 или более последовательных чисел в массиве

Question

у нас есть массив рейтингов, мы должны найти максимальный рейтинг в таком месте, чтобы мы не могли пропустить 1 или более последовательных рейтингов в массиве

Example-1: {9,-1,-3,-4,-5} output = 9 + -1 + -4 = 4

Объяснение: Я взял 9, у нас естьчтобы взять -1 или -3, мы не можем сразу перейти к -4, так как мы не можем пропустить 1 или более последовательных чисел.

Example-2: {-1,-2,-3,-4,-5} output = -2 + -4 = -6  
Example-3: {-3,2,-4,-1,-2,5} output = 2 + -1 + 5 = 6   
Example-4: {9,-1,-3,4,5} output = 9 + -1 + 4 + 5 = 17

Я попробовал приведенный ниже код, но он работает в случае примера: 2,3,4, но не для примера 1, аналогично сбой в другом сценарии.

static int maximizeRatings(int[] ratings) {
    int current = 0;
    boolean result = false;
    for(int j=0; j<ratings.length;j++){
        if(ratings[j]<0){
            result = true;
        }else{
        result = false; 
        }
    }
    if(result){
        return allnegatine(ratings);
    }
    for(int i=0; i<ratings.length;i++){
        if(i == ratings.length-1){
            if(ratings[i] > 0)
                current += ratings[i];
        }else{
        if(ratings[i] >0 && ratings[i+1]>0){
            current = ratings[i]+ratings[i+1];
            i++;
        }
        if(ratings[i] > ratings[i+1]){
            current += ratings[i];
        }else{
            current += ratings[i+1];
            i++;
        }
        }

    }
    return current;
}

private static int allnegatine(int[] ratings) {
    int current =0;
    for(int i=0; i<ratings.length;i++){
        if(ratings.length%2==0){
            if(i%2 == 0)
            current += ratings[i];
        }else{
            if(i%2!=0)
                current += ratings[i];
        }
    }
    return current;
}

не получено исключениедля некоторых сценариев, таких как пример 1, я получаю -6 вместо 4, я пытаюсь получить правильный код, который будет проходить все сценарии.Спасибо

Answer 1

Это проблема динамического программирования.

Пусть dp[i] будет максимальным рейтингом, который может быть достигнут с учетом только той части массива, которая начинается с нуля, заканчивается на i и включает рейтинги [i].

dp[0]=ratings[0]
dp[1]=max(ratings[1],ratings[0]+ratings[1])
dp[i]=max(dp[i-1],dp[i-2])+ratings[i]

Ответ: max(dp[n-1],dp[n-2]) где n - размер массива оценок.

Также вы можете отказаться от массива dp и сохранить 2 переменные для dp [i-1] и дп [i-2].

Answer 2

это типичная проблема рекурсии (при условии, что входной массив достаточно длинный). Вы должны пройти через предметы и попробовать все возможные комбинации, а затем выбрать лучшую.

Поскольку это похоже на типичную школьную работу, я не уверен, стоит ли мне вставлять свое решение. Вы должны понять это сами или, по крайней мере, понять, что происходит, чтобы иметь возможность реализовать это самостоятельно в следующий раз.

public class RatingService {

    public int calculate(List<Integer> input) {
        return recursion(input, true, 0);
    }

    private int recursion(List<Integer> sublist, boolean canSkip, int sum) {
        if (sublist.isEmpty()) {
            return sum;
        }
        int skippedSum = Integer.MIN_VALUE;
        int notSkippedSum;
        Integer integer = sublist.get(0);

        if (canSkip) {
            skippedSum = recursion(sublist.subList(1, sublist.size()), false, sum);
        }
        notSkippedSum = recursion(sublist.subList(1, sublist.size()), true, integer + sum);

        return skippedSum > notSkippedSum ? skippedSum : notSkippedSum;
    }
    }

Answer 3

Я думаю, что вы делаете ошибку, проверяя все отрицательные числа в цикле for. Если последний элемент в массиве отрицательный, тогда переменная «result» будет иметь значение true, что означает, что весь массив отрицательный, но на самом деле это не так.

Вы должны заменить цикл for на:

for(int j=0;j<ratings.length;j++){
    if(ratings[j]<0){
        result=true;
    }
    else{
        result = false;
        break;
    }
    }

Он прервет цикл for в индексе, где он найдет любое положительное число i-e: все элементы массива не являются отрицательными.