public static int maxDonations1(int[] donations) {
    if (donations == null || donations.length == 0) return 0;
    else if (donations.length == 1) return donations[0];
    else if (donations.length == 2) return donations[0] > donations[1] ? donations[0]
        : donations[1];

    // 0~n-2
    int[] d1 = new int[donations.length];
    d1[0] = donations[0];
    d1[1] = donations[1];
    d1[2] = donations[0] + donations[2];
    for (int i = 3; i < donations.length - 1; i++) {
      d1[i] = Math.max(d1[i - 2], d1[i - 3]) + donations[i];
    }

    // 1~n-1
    int[] d2 = new int[donations.length];
    d2[0] = 0;
    d2[1] = donations[1];
    d2[2] = donations[2];
    for (int i = 3; i < donations.length; i++) {
      d2[i] = Math.max(d2[i - 2], d2[i - 3]) + donations[i];
    }

    return Math.max(d1[donations.length - 2], d2[donations.length - 1]);
  }