leetcode 1186：删除一次得到子数组最大和
题目描述：
给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。
示例 1：
输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
示例 2：
输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接选出 [3]，这就是最大和。
示例 3：
输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。
提示：
1 <= arr.length <= 105
-104 <= arr[i] <= 104
思路： 二维DP
dp[i][2] 状态定义成二维的，因为可能已经删除过一个，可能还没有删除过
dp[i][0]: 以i为结尾的子数组没有删除过最大和
dp[i][1]:以i为结尾的子数组删除过一次最大和
此题此外还需要注意的是需要保证最后的数组的长度不能是0，所以在初始化的时候做了一点处理，对长度为1（题目中说长度是>= 1的）时进行了求解。
剩下的部分正常进行状态转移
import sys
maxint = sys.maxsize
class Solution:
def maximumSum(self, arr: List[int]) -> int:
dp = [[-maxint for _ in range(2)] for _ in range(len(arr))]
# dp[i][0]到i还没有删除过 dp[i][1]表示已经删除过一次
if len(arr) == 1:
return arr[0]
dp[0][0] = arr[0]
dp[0][1] = 0
dp[1][0] = max(arr[0]+arr[1], arr[1])
dp[1][1] = max(arr[0], arr[1])
res = max(dp[1][0], dp[1][1])
for i in range(2, len(arr)):
dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i]) #接着之前的继续，还是自己开始
dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0]) # 不删除这次的值和之前已经删除的情况相加，或者删除这次的值
res = max(res, dp[i][0], dp[i][1])
return res
思路参考的题解链接
leetcode 376：摆动序列
题目描述：
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
思路： DP
状态定义：
dp[i][2]: 表示到i时摆动序列的最大长度，可以有i也可以没有i
dp[i][0]: 表示考虑到i，且最后一部分是上升的时候最大摆动序列长度
dp[i][1]: 表示考虑到i，且最后一部分是下降的时候最大摆动序列长度
在进行状态转移的时候，两者需要调用，因为需要考虑现在的增或者减的情况
import sys
maxint = sys.maxsize
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
dp = [[-maxint for _ in range(2)] for _ in range(len(nums))]
if len(nums) == 1:
return len(nums)
dp[0][0], dp[0][1] = 1, 1
res = 1
for i in range(1, len(nums)):
for j in range(i): # 需要考虑i之前的所有可能的情况 因为可能之前的元素又饿时候是没有算进去的
if nums[i] - nums[j] > 0:
dp[i][0] = max(dp[j][1] + 1, 1, dp[i][0])
elif nums[i] - nums[j] < 0:
dp[i][1] = max(dp[j][0] + 1, 1, dp[i][1])
elif nums[i] - nums[j] == 0:
dp[i][0] = 1
dp[i][1] = 1
res = max(res, dp[i][0], dp[i][1])
return res
时间复杂度是O(n^ 2)。
进一步想要减小时间复杂度至O(1)。
参考题解思路链接
画个图仔细思考一下确实是这样
相应的代码：
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
dp = [[0 for _ in range(2)] for _ in range(len(nums))]
if len(nums) == 1:
return len(nums)
res = 0
for i in range(1, len(nums)):
if nums[i] - nums[i-1] > 0:
dp[i][1] = dp[i-1][0] + 1
dp[i][0] = dp[i - 1][0]
elif nums[i] - nums[i-1] < 0:
dp[i][0] = dp[i-1][1] + 1
dp[i][1] = dp[i-1][1]
elif nums[i] - nums[i-1] == 0:
dp[i][0] = dp[i-1][0]
dp[i][1] = dp[i-1][1]
res = max(dp[-1][0], dp[-1][1]) + 1
return res
时间复杂度是O(n)，空间复杂度可以进一步优化，将dp数组转换成用两个数进行。
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
dp0, dp1 = 0, 0
if len(nums) == 1:
return len(nums)
for i in range(1, len(nums)):
if nums[i] - nums[i-1] > 0:
dp1 = dp0 + 1
elif nums[i] - nums[i-1] < 0:
dp0 = dp1 + 1
res = max(dp0, dp1) + 1
return res