[leetcode] 1191. K-Concatenation Maximum Sum

[leetcode] 1191. K-Concatenation Maximum Sum

Description

Given an integer array arr and an integer k, modify the array by repeating it k times.

For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [1,2], k = 3Output: 9

Example 2:

Input: arr = [1,-2,1], k = 5Output: 2

Example 3:

Input: arr = [-1,-2], k = 7Output: 0

Constraints:

1 <= arr.length <= 10^51 <= k <= 10^5-10^4 <= arr[i] <= 10^4

分析

题目的意思是：给定一个数组，可以被重复K次，求生成的数组的最长子数组的和。暴力求解的话肯定是拼接后用一个求和的Kadane算法算出最大值就行了。

另外一种思路是分析K=1这种情形和K=2这两种情形就行了，后面的类似。分别用kadane算法就行了；最后还有一种情形，如果整个数组的和为正并且K大于2，其和为sum，那么长度和为cur+sums*(k-2).

代码

class Solution: def kConcatenationMaxSum(self, arr: List[int], k: int) -> int: n=len(arr) cur=0 sums=0 maxSum=max(arr[0],0) for i in range(min(k,2)*n): if(i==0): maxSum=max(arr[i],0) else: maxSum=max(maxSum+arr[i%n],arr[i%n]) cur=max(cur,maxSum) if(i0): for i in range(2,k): cur=(cur+sums)%(10**9+7) return cur

参考文献

​​[LeetCode] Kadane算法与解题思路​​​​算法面试题——动态规划Kadane’s algorithm​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。