记忆化搜索解法

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    static int N;
    static int[] a;
    static int[] mem;
    static int f(int x) {
        if (mem[x] != 0) return mem[x];
        int sum = 0;
        if (x > N)  sum = 0;
        else sum = Math.max(f(x + 1), f(x + 2) + a[x]);
        mem[x]= sum;
        return sum;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- != 0) {
            N = sc.nextInt();
            a = new int[N + 1];
            mem = new int[N + 5];
            for (int i = 1; i <= N; i++) {
                a[i] = sc.nextInt();
            }
            Arrays.fill(mem,0);
            System.out.println(f(1));
        }
    }
}