LeetCode-1191. K-Concatenation Maximum Sum

LeetCode-1191. K-Concatenation Maximum Sum

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^5​​​​1 <= k <= 10^5​​​​-10^4 <= arr[i] <= 10^4​​

题解：

这种数据量直接拼接肯定超时。

这题类似于环形合并石子问题我们只需要分析两个拼接的即可。

如果总串和sum大于0，那么返回两串拼接后最大值（可能尾部并不衔接）加上sum。

如果小于等于0，那么直接返回两串的最大值。

class Solution {public: long long mod = 1000000007; int kConcatenationMaxSum(vector& arr, int k) { int n = arr.size(); long long sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; } long long res = 0, t = 0; for (int i = 0; i < 2 * n; i++) { if (t + arr[i % n] > 0) { t += arr[i % n]; res = max(res, t); } else { t = 0; } } if (sum <= 0) { return res % mod; } else { return (res + sum * ((k - 2) > 0 ? k - 2 : 0)) % mod; } }};

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