链接：LeetCode
[Leetcode]5392. 分割字符串的最大得分
给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。
「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。
在遍历过程中，动态维护左边的0的总数和右侧1的总数。
class Solution:
def maxScore(self, s: str) -> int:
res = result = 0
count_1 = s.count('1')
result_0 = result_1 = 0
for i in range(len(s)-1):
if s[i] == '0':
result_0 += 1
else:
result_1 += 1
result = result_0 +(count_1-result_1)
res = max(res,result)
return res
[Leetcode]5393. 可获得的最大点数
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
滑动窗口，维护一个len-k的窗口，保证窗口里面和最小，然后剩余的k个数的和就是最大。
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
n = len(cardPoints)
res = sum(cardPoints)
if k>=n:return res
minresult = result = sum(cardPoints[:n-k])
for i in range(n-k,n):
result += cardPoints[i] - cardPoints[i-(n-k)]
minresult = min(minresult,result)
return res - minresult
[Leetcode]5394. 对角线遍历 II
给你一个列表 nums ，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。
根据矩形的特点，设行的标号为i，列的标号为j。则对于每一条对角线而言，i + j的值是唯一的。接下来排序即可。
import collections
class Solution:
def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
dic = collections.defaultdict(list)
# 根据主对角线坐标特性，将横纵方向坐标和相同的放在一组
for row in range(len(nums)):
for col in range(len(nums[row])):
dic[row + col].append(nums[row][col])
res = []
# 按字典的 key 排序进行遍历，取出的就是按题意由左下到右上方↗一组一组的值
for key in sorted(list(dic.keys())):
res.extend(dic[key][::-1]) # 由于存的时候是先遍历的存到前面，按题目要求需要返回来，所以取[::-1]
return res
[Leetcode]5180. 带限制的子序列和
给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数(nums[i])和(nums[j])，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。
数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。
结合了动态规划和滑动窗口的思想。
首先定义动态规划转移方程,dp[i]表示以i数字结尾的最大子序列，则转移方程为：
如果直接遍历i的前k个值，然后取最大值会超时，所以我们需要用一个结构来维持前k个值的大小顺序，从而直接获取前k个最大的值，这就回归到了LeetCode239题的问题。
class Solution:
def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
dp = [0]*len(nums)
dp[0] = nums[0]
arr = [(nums[0],0)]
for i in range(1,len(nums)):
M = arr[0][0]
if M>=0:dp[i] = M+nums[i]
else:dp[i] = nums[i]
while arr and dp[i]>=arr[-1][0]:
arr.pop()
arr.append((dp[i],i))
while arr[0][1]<(i-k+1):
arr.pop(0)
return max(dp)
参考：
leetcode