牛客-超级跳

链接：https://www.nowcoder.com/questionTerminal/2ae94400de4e409c91c3470a95681bfc
来源：牛客网

Abby经常做奇怪的梦。
有一天她梦到了自己遇到了一个巫婆，巫婆告诉她，有一种含有弹跳能量的药水，可以改变Abby的弹跳能力。
这种药水在奇数时刻服用可以增加弹跳力，但是再偶数的时刻服用反而会下降弹跳能力。
同时这种药水一旦开始服用就需要连续服用，不可以间断，不可以重复服用，也不可以调换药水瓶的顺序，但是可以向后跳过一瓶或者多瓶药水。

初始的时刻是从1开始的，Abby初始的弹跳能力是0，当然我们的Abby总想尽可能的跳的高一些。

输入描述:
一个单一的数字P(1 <= P <= 500,000）
第2…P+1行，每行有一个数字（数字小于500），表示每瓶药水的弹跳能量，即可以改变的弹跳力

输出描述:
单个整数，表示最大可能的弹跳力
（计算过程以及最终结果均在int32的取值范围内）

输入
8
7
2
1
8
4
3
5
6
输出
17

备注：药水选择为 7 - 1 + 8 - 3 + 6 = 17

import java.util.Scanner;

public class test {
    public static void main(String[] args) {
        // 输入数组
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        int add = 0;
        for(int i=0;i<n;i++){
            try {
                arr[i] = in.nextInt();
            } catch (Exception e) {
                add=1;
                break;
            }
        }
        int[][] cache = new int[arr.length+1][2];
        int res = 0;
        res = process(arr,cache);
        System.out.println(res+add);
    }
    // 处理过程
    public static int process(int[] arr,int[][] cache){
        for(int x=cache.length-2;x>=0;x--){
            for(int y=0;y<=1;y++){
                int tmp = y==1 ? arr[x] : -arr[x];
                cache[x][y] = Math.max(cache[x + 1][y], tmp + cache[x + 1][y == 1 ? 0 : 1]);
                System.out.println("cache["+x+"]["+y+"]="+cache[x][y]);

            }
        }
        return cache[0][1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

对于每个数，都可以有正负两种状态。要是为负的话，是Math.max(后一个数为负状态的值，后一个数为正状态的值加上这个负数的值)，要是为正的话，是Math.max(后一个数为正状态的值，后一个数为负状态的值加上这个正数的值)。最后是cache[0][1]，因为第一个状态一定是正数状态。