Description
給定一個陣列
nums，子序列的交替和定義為奇數索引位置的元素之和減去偶數索引位置的元素之和（子序列自身的索引從 0 開始）。回傳最大交替子序列和。
Example:
Input: nums = [4,2,5,3] Output: 7 (子序列 [4,2,5]，交替和 = 4 - 2 + 5 = 7)
Intuition#
維護兩個狀態：下一個要加的（偶數位）和下一個要減的（奇數位）的最大交替和。
even：下一個選的元素要加（+），此時的最大交替和odd：下一個選的元素要減（-），此時的最大交替和- 對每個元素，可以選或不選，更新兩個狀態
Approaches#
1: 2D DP#
- 概念:
dp[i][0]表示考慮前i個元素，下一個要加的最大值；dp[i][1]表示下一個要減的最大值。 - 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun maxAlternatingSum(nums: IntArray): Long {
val n = nums.size
val dp = Array(n + 1) { LongArray(2) }
for (i in 1..n) {
dp[i][0] = maxOf(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]) // 不選 or 從 odd 狀態選（加）
dp[i][1] = maxOf(dp[i - 1][1], dp[i - 1][0] - nums[i - 1]) // 不選 or 從 even 狀態選（減）
}
return maxOf(dp[n][0], dp[n][1])
}
}⭐2: 空間優化 DP#
- 概念: 只需兩個變數
even和odd記錄狀態。 - 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun maxAlternatingSum(nums: IntArray): Long {
var even = 0L // 下一個選的元素會被加
var odd = 0L // 下一個選的元素會被減
for (num in nums) {
val newEven = maxOf(even, odd + num)
val newOdd = maxOf(odd, even - num)
even = newEven
odd = newOdd
}
return maxOf(even, odd)
}
}🔑 Takeaways#
- Pattern: 狀態機 DP — 類似買賣股票問題，維護「加」和「減」兩個狀態
- 關鍵技巧: 交替子序列的選擇等價於在「要加」和「要減」兩個狀態之間轉換；與股票題的 hold/not-hold 結構相同