做电商网站用什么系统,临沂网站开发公司电话,广州网站优化排名系统,上海高端网站开发公司Leetcode 3077. Maximum Strength of K Disjoint Subarrays 1. 解题思路 1. 朴素思路2. 算法优化 2. 代码实现 题目链接#xff1a;3077. Maximum Strength of K Disjoint Subarrays
1. 解题思路
这道题很惭愧没有搞定#xff0c;思路上出现了差错#xff0c;导致一直没能…Leetcode 3077. Maximum Strength of K Disjoint Subarrays 1. 解题思路 1. 朴素思路2. 算法优化 2. 代码实现 题目链接3077. Maximum Strength of K Disjoint Subarrays
1. 解题思路
这道题很惭愧没有搞定思路上出现了差错导致一直没能搞定最后是看了大佬的算法才搞定的唉不过确实比较巧妙因此这里把我们的朴素实现思路和大佬们的思路都在这里整理一下留个记录。
1. 朴素思路
首先我拿到这道题目之后的一个朴素的思路就是动态规划显然我们就是要将一个长度为n的arr分成k段然后在每段当中获取最大/最小的subarray的和然后乘以因子之后求和获取最大值。
因此我们用一个动态规划即可处理这个问题。
然后对于中间的每一个subarry对于如何其中最大最小值的问题我们用一个累积数组就可以将问题转换为如何求一个array的任意元素之后最大/最小元素的问题这个是简单的。
因此我们就可以快速给出代码如下
class Solution:def maximumStrength(self, nums: List[int], k: int) - int:n len(nums)s list(accumulate(nums, initial0))factors [(i1)*(-1)**(i%2) for i in range(k)]print(s)lru_cache(None)def dp(idx, r):if r 0:return 0ans -math.infif r % 2 1:_min s[idx]sub -math.inffor i in range(idx1, n-r2):sub max(sub, s[i] - _min)_min min(_min, s[i])ans max(ans, factors[r-1] * sub dp(i, r-1))else:_max s[idx]sub math.inffor i in range(idx1, n-r2):sub min(sub, s[i] - _max)_max max(_max, s[i])ans max(ans, factors[r-1] * sub dp(i, r-1))return ansans dp(0, k)return ans不过这段代码遇到了超时问题无法正常通过。
其原因在于虽然动态规划的总的时间复杂度是 O ( N K ) O(NK) O(NK)但是由于内部还有一重循环导致最坏的情况下时间复杂度变成了 O ( N 2 K ) O(N^2K) O(N2K)这显然就无法通过测试样例了。
2. 算法优化
而大佬的思路则是和我们相反的我们是考虑如何将整体的array进行分段大佬的思路则是考察array当中每一个元素的归属显然这只有以下几种情况
哪个subarray都不属于属于某一个subarray 与前一个元素都属于同一个subarray是一个新的subarray第一个元素
此时我们只需要给出两个 k k k维的动态规划向量dp0, dp1对于某一个元素他们的任意一维i分别表示
dp0[i]表示当前元素属于第 i i i个subarray时能够获得的最大strengthdp1[i]表示之前所有元素被分为 i i i个subarray时能够获得的最大strength
此时我们显然有迭代关系 d p 0 t ( i ) α ⋅ n i m a x ( d p 0 t − 1 ( i ) , d p 1 t ( i − 1 ) ) d p 1 t ( i ) m a x ( d p 1 t − 1 ( i ) , d p 0 t ( i ) ) \begin{aligned} dp0_{t}(i) \alpha \cdot n_i \mathop{max}(dp0_{t-1}(i), dp1_{t}(i-1)) \\ dp1_{t}(i) \mathop{max}(dp1_{t-1}(i), dp0_{t}(i)) \end{aligned} dp0t(i)dp1t(i)α⋅nimax(dp0t−1(i),dp1t(i−1))max(dp1t−1(i),dp0t(i))
由此遍历整个长度为n的array我们即可从dp1中得到其所有元素被分至 k k k个subarray时能够获得的最大strength。
我们将其翻译为代码语言即可。
2. 代码实现
给出python代码实现如下
class Solution:def maximumStrength(self, nums: List[int], k: int) - int:factors [(k-i)*(-1)**(i%2) for i in range(k)]# dp0 stand for consecutive and dp1 for inconsecutivedp0 [-math.inf for _ in range(k)]dp1 [-math.inf for _ in range(k)]for num in nums:# s[i] stand for max result including num in ith subarrays [-math.inf for _ in range(k)]s[0] num * factors[0] max(0, dp0[0])for i in range(1, k):s[i] num * factors[i] max(dp0[i], dp1[i-1])for i in range(k):dp1[i] max(dp1[i], s[i])dp0 sreturn dp1[-1]提交代码评测得到耗时2386ms占用内存18MB。
