教你做美食的网站,网站开发及应用,天津住房和城乡建设建造师网站,短视频营销文章目录1. 题目2. 解题1. 题目
给你一个整数数组 arr 和一个整数 k。
首先#xff0c;我们要对该数组进行修改#xff0c;即把原数组 arr 重复 k 次。
举个例子#xff0c;如果 arr [1, 2] 且 k 3#xff0c;那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。
然后#x…
文章目录1. 题目2. 解题1. 题目
给你一个整数数组 arr 和一个整数 k。
首先我们要对该数组进行修改即把原数组 arr 重复 k 次。
举个例子如果 arr [1, 2] 且 k 3那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。
然后请你返回修改后的数组中的最大的子数组之和。
注意子数组长度可以是 0在这种情况下它的总和也是 0。
由于 结果可能会很大所以需要 模mod 10^9 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 10^5
1 k 10^5
-10^4 arr[i] 10^4来源力扣LeetCode 链接https://leetcode-cn.com/problems/k-concatenation-maximum-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
分三种情况
k1, k 2, k 2
class Solution {
public:int kConcatenationMaxSum(vectorint arr, int k) {typedef long long ll;vectorll presum(arr.size()*2);ll ans max(0, arr[0]), mod 1e97, sum0;ll MIN min(0, arr[0]), n arr.size();presum[0] arr[0];for(int i 1; i n*2; i){presum[i] presum[i-1] arr[i%n];//前缀和ans max(ans, (ll) (presum[i]-MIN));//前缀和减去前面的最小的前缀和, 最大子数组和MIN min(MIN, (ll) presum[i]);if(k1 i n-1)return ans;// k1直接返回答案if(in-1)sum presum[n-1];//记录单个完整数组的和}if(sum 0)//和能带来收益return (ans(k-2)*sum%mod)%mod;return ans;}
};96 ms 44.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
