LC.P1911[最大子序列交替和]

方法一:动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public long maxAlternatingSum(int[] nums) {
int n = nums.length;
// dp[i][0]表示以最后一个元素下标为偶数的子序列和
// dp[i][1]表示以最后一个元素下标为奇数的子序列和
long[][] dp = new long[n][2];
dp[0][0] = nums[0];
dp[0][1] = 0;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
dp[i][0] = Math.max(dp[i - 1][1] + nums[i], dp[i - 1][0]);
dp[i][1] = Math.max(dp[i - 1][0] - nums[i], dp[i - 1][1]);
}
}
// 最终选择的序列一定不可能位于奇数下标(因为奇数下标需要减去该值)
return dp[n - 1][0];
}
}
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$

方法二:滚动数组(优化)

1
2
3
4
5
6
7
8
9
10
class Solution {
public long maxAlternatingSum(int[] nums) {
long even = nums[0], odd = 0;
for (int i = 1; i < nums.length; i++) {
even = Math.max(odd + nums[i], even);
odd = Math.max(even - nums[i], odd);
}
return even;
}
}
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$