问TCS MockVita 2019第二轮问题:跳跃游戏

EN

我正在尝试解决在TCS MockVita 2019第二轮中提出的问题：

问题描述

高斯学校的数学老师Felix Kline博士介绍了下面的游戏来教他的学生解决问题。他将一系列的“跳石”(纸片)放在一条线上，每一块石头上都标有点(正数)。

学生从一端开始，然后跳到另一端。一个人可以踩在一块石头上，把石头上的数字加到他们的累积分数上，或者跳过一块石头，落在下一块石头上。在这种情况下，他们得到了他们落地的石头上标记的两倍的分数，但没有得到他们跳过的石头上标记的分数。

在旅途中，学生最多可以(如果他们选择)做一次“双跳”-即，他们跳过两个连续的石头-在那里他们将获得他们着陆的石头的三倍的分数，但不是他们跳过的石头的分数。

老师希望他的学生进行一些思考，并想出一个尽可能获得最高分数的计划。给定石头序列上的数字，编写一个程序来确定可能的最大分数。

约束条件

sequence<中的石块数30

输入格式

第一行包含N，整数的数量(这是一个正整数)

下一行包含用逗号分隔的N个点(每个点是一个正整数)。这些是石头上的点，按照石头的放置顺序。

输出

一个表示最高分数的整数

测试用例

解释

示例1

输入

3.

4,2,3

输出

10

解释

有3块石头(N=3)，点(按布局顺序)分别为4、2和3。

如果我们踩到第一块石头，跳过第二块石头，得到4+2 x 3= 10。两次跳到第三块石头只会得到9。因此结果是10，不使用双重跳跃

示例2

输入

6

4,5,6,7,4,5

输出

35

解释

N=6，点的顺序是given.One获得35的方法是从双跳开始跳到石头3 (3 x 6=18)，跳到石头4 (7)，然后跳到石头6 (10分)，总共35分。两次跳跃只使用了一次，结果是35。

我发现这是一个动态编程问题，但我不知道我做错了什么，因为我的解决方案无法通过所有测试用例。我的代码通过了我创建的所有测试。

unordered_map<int, int> lookup;
int res(int *arr, int n, int i){

    if(i == n-1){
        return 0;
    }

    if(i == n-2){
        return arr[i+1];
    }

    if(lookup.find(i) != lookup.end())
        return lookup[i];

    int maxScore = 0;

    if(i< n-3 && flag == false){
        flag = true;
        maxScore = max(maxScore, 3 * (arr[i+3]) + res(arr, n, i+3));
        flag = false;
    }
    maxScore = max(maxScore, (arr[i+1] + res(arr,n,i+1)));

    lookup[i] = max(maxScore, 2 * (arr[i+2]) + res(arr, n, i+2));

    return lookup[i];
}

cout << res(arr, n, 0) + arr[0];  // It is inside the main()

我希望你能找到我的代码中的错误，并给出正确的解决方案，以及任何未能通过该解决方案的测试用例。谢谢:)