题解 | #不相邻最大子序列和# [P3 - T2]

JAVA - DP Solution, O(n) time, O(1) space

请输出不相邻最大子序列和

递归逻辑
f(0) = max(array[0], 0);
f(1) = max(array[1], 0);
f(2) = max(array[2], 0) + max(f(0));
f(3) = max(array[3], 0) + max(f(0), f(1));
f(4) = max(array[4], 0) + max(f(0), f(1), f(2));
... ...
f(x) = max(array[x], 0) + max(f(0), ... f(x-2));

可见DP只需要存两个state，一个是走到x为止的max，一个是走到x-2为止的max。

public class Solution {

    public long subsequence (int n, int[] array) {
      if (n == 0) return 0;
      
      long max = Math.max(array[0], 0);
      long max_lag2 = 0;
      
      for (int i = 1; i < n; i++) {
        long cur = Math.max(array[i], 0) + max_lag2;
        
        // 此时max还是i-1时的值
        // i.e. i+1用的max_lag2对应i-1的max
        max_lag2 = max;
        max = Math.max(cur, max);
      }
      
      return max;
    }
}