给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
注意:
数组长度 n 满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:
我要评论输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
思路：
首先分析题意，可以得出结论，结果必定落在**【max（nums）， sum（nums）】**这个区间内，因为左端点对应每个单独的元素构成一个子数组，右端点对应所有元素构成一个子数组。
然后可以利用二分查找法逐步缩小区间范围，当区间长度为1时，即找到了最终答案。
每次二分查找就是先算一个mid值，这个mid就是代表当前猜测的答案，然后模拟一下划分子数组的过程，可以得到用这个mid值会一共得到的子区间数cnt，然后比较cnt和m的关系，来更新区间范围。
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
# max(nums), sum(nums)
if len(nums) == m:
return max(nums)
left = max(nums)
right = sum(nums)
while left < right:
mid = (left + right) // 2 # 最大和
# 开始模拟切分数组
temp = 0 # 初始第一个子数组和
cnt = 1 # 数组个数初始化为1，说明还没有进行切分
for num in nums:
temp += num # 累加元素求和
if temp > mid: #说明当前这个子数组的和已经超过了允许的最大值mid，需要把当前元素放在下一个子数组里
temp = num # 此时的num不能加入到当前子数组，要放到下一个子数组里
cnt += 1 # 切分了一个数组，cnt+1
# 切分数组结束
if cnt > m: # 说明分出了比要求多的子数组，多切了几刀，说明mid应该加大，这样能使子数组的个数减少
left = mid + 1
elif cnt <= m:
right = mid
return left
其他类似题目
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
示例 1：
输入: piles = [3,6,7,11], H = 8
输出: 4
示例 2：
输入: piles = [30,11,23,4,20], H = 5
输出: 30
示例 3：
输入: piles = [30,11,23,4,20], H = 6
输出: 23
思路：
最小速度是1，最大速度是max(piles)，取中间速度，判断是否能在H小时内完成，如果可以，缩紧右边界，如果不可以，缩紧左边界，加快速度。
class Solution:
def minEatingSpeed(self, piles: List[int], H: int) -> int:
left = 1
right = max(piles) + 1
while left < right:
mid = left + (right - left) // 2
# 以speed是否能在 H ⼩时内吃完⾹蕉
if self.canFinish(piles, mid, H):
right = mid
else:
left = mid + 1
return left
def canFinish(self, piles, speed, H):
# 以speed是否能在 H ⼩时内吃完⾹蕉
time = 0
for n in piles:
# 没吃完剩下的还得一小时
remain = 0
if n % speed != 0:
remain = 1
time += n // speed + remain
if time > H:
return False
return time <= H
给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例：
输入：[8,1,5,2,6]
输出：11
解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
思路：
咋一看，很简单，代码撸完，超时
可以重新组合得分公式：（A[i] + i ）+ （A[j] - j）
这样就可以看成是左A[i]+i和右A[j]-j两部分和的最大值。这里A[i] + i 和 A[j] - j 相互独立
考虑约束条件i < j，于是形成动态规划的思路：
好了，看代码
def maxScoreSightseeingPair(self, A: List[int]) -> int:
# 暴力超时解法
# n = len(A)
# score = -float('inf')
# for i in range(n - 1):
# for j in range(i + 1, n):
# score = max(score, A[i] + A[j] + i - j)
# return score
# A[i]+i+A[j]-j
left = A[0] + 0
res = -1
for j in range(1, len(A)):
res = max(res, left + A[j] - j)
left = max(left, A[j] + j)
return res
本文地址：https://blog.csdn.net/andyjkt/article/details/107576251
如对本文有疑问， 点击进行留言回复！！
Python sqlalchemy时间戳及密码管理实现代码详解
网友评论