java - 在我们不能跳过数组中 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 数组并为 dp[i-1] 和 dp[i-2] 保留 2 个变量。