给你一个整数数组 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：很有趣的动态规划求子区间和，但是题目扩大了数据量，可以发现一个规律，初始数组最大为1e5，如果k比较小，可以直接暴力找答案，因为传统的动态规划思想求最大子区间和的时间复杂度是O(n)，是没问题，如果K很大了，可以证明一个求解方法，如果K>=3，实际只需要把初始数组复制3次就可以了，然后用我们传统的方法去找最大子区间和并且标注出这个最大子区间和的左右位置，如果左右位置已经横跨了单个数组长度，说明单个数组长度是有意义的，比如，下列：
原始数组
[x0,x1,x2,x3,x4] ,k=100
复制3次得到：
[x0,x1,x2,x3,x4,x0,x1,x2,x3,x4,x0,x1,x2,x3,x4]
我们单纯对上述数组求解，如果得到的最大子区间左右位置为（下标从0开始）[2,11]，说明中间的部分的单个数组是被利用了的，是有意义的，那么我就可以把剩下的k-3次的单个数组和加进来扩大，如果没有横跨单个数组长度，说明单个数组总和为负值，没必要再复制了，直接返回当前答案。不难理解。

AC代码

class Solution {
public:
typedef long long ll;
const ll mod=1e9+7;
vector<int>q;
int kConcatenationMaxSum(vector<int>& arr, int k) 
{q.clear();if(k<=2){for(int i=0;i<k;i++)q.insert(q.end(),arr.begin(),arr.end());ll ans=0,mx=0;for(int i=0;i<q.size();i++){ans+=q[i];if(ans<0)ans=0;mx=max(mx,ans);}return mx%mod;}else{for(int i=0;i<3;i++)q.insert(q.end(),arr.begin(),arr.end());int l=0,r=0,signl=0,signr=0;ll ans=0,mx=0;for(int i=0;i<q.size();i++){ans+=q[i];if(ans<0){signl=i+1;ans=0;}signr=i;if(ans>mx){r=signr;l=signl;mx=ans;}}if((r-l+1)>arr.size()){ans=0;for(int i=0;i<arr.size();i++)ans+=arr[i];mx-=ans;mx+=((k-2)*ans);}return mx%mod;}return 0;
}
};