Leetcode.1191 K 次串联后最大子数组之和

题目链接

Leetcode.1191 K 次串联后最大子数组之和 Rating ： 1748

题目描述

给定一个整数数组 arr和一个整数 k，通过重复 k次来修改数组。

例如，如果 arr = [1, 2] ， k = 3，那么修改后的数组将是 [1, 2, 1, 2, 1, 2]。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大，需要返回的 109+710^9 + 7109+7 的 模 。

示例 1：

输入：arr = [1,2], k = 3
输出：9

示例 2：

输入：arr = [1,-2,1], k = 5
输出：2

示例 3：

输入：arr = [-1,-2], k = 7
输出：0

提示：

• 1<=arr.length<=1051 <= arr.length <= 10^51<=arr.length<=105
• 1<=k<=1051 <= k <= 10^51<=k<=105
• −104<=arr[i]<=104-10^4 <= arr[i] <= 10^4−104<=arr[i]<=104

解法：前缀和 + 贪心

分情况讨论：

• 当最大子数组 只位于单个数组内 时，此时 最大和 就为单个数组内的最大子数组和。
• 当最大子数组 横跨两个数组 时，此时 最大和 就为 第一个数组的最大后缀和 + 第二个数组的最大前缀和。
• 当最大子数组 横跨多个数组 时，此时 单个数组的和肯定是大于 0的，此时 最大和 就为 第一个数组的最大后缀和 + （k - 2）个数组的数组和 + 最后一个数组的最大前缀和。

如何计算一个数组内的最大子数组和

时间复杂度：$O(n)$

C++代码：

const int MOD = 1e9 + 7;
using LL = long long;class Solution {
public:int kConcatenationMaxSum(vector<int>& arr, int k) {int n = arr.size();//前缀和 最大前缀和 最小前缀和LL preSum = 0,maxPreSum = 0, minPreSum = 0;//单个数组的最大数组和LL ans = 0;for(auto x:arr){preSum += x;minPreSum = min(preSum,minPreSum);maxPreSum = max(preSum,maxPreSum);ans = max(ans,preSum - minPreSum);}//后缀和  最大后缀和 LL suffixSum = 0 , maxSuffixSum = 0;for(int i = n - 1;i >= 0;i--){suffixSum += arr[i];maxSuffixSum = max(suffixSum,maxSuffixSum);}//1.单个数组的最大和 即 ans//2.两个数组的最大和 即第一个数组的最大后缀和 + 第二个数组的最大前缀和if(k >= 2) ans = max(ans,maxPreSum + maxSuffixSum);//3.多个数组的最大和 单个数组和 > 0 ， 即第一个数组的最大后缀和 + (k-2)个数组的和 + 最后//一个数组的最大前缀和if(k >= 3 && preSum > 0) ans = max(ans , maxSuffixSum + (k-2)*preSum + maxPreSum);return (int)(ans % MOD);}
};