给一个数组，在这个数组中选组合，不能选相邻的数，问哪种组合累加和最大？

    dp[i] : arr[0 ~ i] 的所有组合中最大的累加和

    • 1） 只包括arr[ i ]
    • 2) 完全不要arr[ i ],———> dp[i - 1]

    • 3) arr[ i ] + dp[i - 2]

    • 技巧：凡是子数组问题就想以每个位置i结尾求一遍，

      1. - 但是这种子序列，组合这种不连续的，你就可以从 0 ~i 范围这个角度入手
    1. public static int maxSum(int[] arr) {
    2.     if (arr == null || arr.length == 0) {
    3.         return 0;
    4.     }
    5.     int N = arr.length;
    6.     if (N == 1) {
    7.         return arr[0];
    8.     }
    9.     if (N == 2) {
    10.         return Math.max(arr[0], arr[1]);
    11.     }
    12.     int[] dp = new int[N];
    13.     dp[0] = arr[0];
    14.     dp[1] = Math.max(arr[0], arr[1]);
    15.     for (int i = 2; i < N; i++) {
    16.         int p1 = arr[i];
    17.         int p2 = dp[i - 1];
    18.         int p3 = arr[i] + dp[i - 2];
    19.         dp[i] = Math.max(Math.max(p1, p2), p3);
    20.     }
    21.     return dp[N - 1];
    22. }