LeetCode-1191 K 次串联后最大子数组之和

╰+攻爆jí腚メ 2024-04-19 08:17 72阅读 0赞

**题目描述：**

给你一个整数数组 `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`

**题目大意：**

将原来的数组扩大为原来的k倍形成一个新的数组，问新数组的最大字段和。

**思路：**

此题很容易让人想到暴力，先形成新数组再对新数组调用最大字段和算法，其实复杂度还可以往下降，看到这道题我就想起了2019ACM山东省赛的C题名字貌似是Wandering Robot，这道题给我的感觉跟那道题很相似，都是**分析一下“头”，分析一下“尾”，中间过程不用详细考究**。

对于这道题来说，上来先看一下原数组所有元素之和是否大于0。

如果大于0直观上则代表着k越大最后的字段和就越大，每一个周期都是可以使子段和增加的。此时最终的最大字段和就是中间k-2个周期的和，再加上第一个周期的尾和最后一个周期的头（前提是加上要使结果更大）；

如果小于0则直观上则代表着k越大最后的子段和就越小，这个时候可以计算两个周期的最大字段和（前提是k>=2），之所以计算两个周期的，是因为一个周期不足以代表最后的最大字段和。举个例子，原数组为\{ **3,6**,-50,-30,-20,1,5\}，原数组的最大子段和是3+6=9，而两个周期合并后的数组为\{3,6,-50,-30,-20,**1,5,3,6**,-50,-30,-20,1,5\}，最大子段和为1+5+3+6=15。

**如果k=1即只有一个周期，直接返回原数组的最大子段和即可**。

**上AC代码：**

class Solution {
    public:
        int dp[200000];
        int kConcatenationMaxSum(vector<int>& arr, int k) {
            int len=arr.size();
            int num=0;
            int i;
            int ans=-0x3f3f3f3f;
            memset(dp,0,sizeof(dp));
            for(i=0;i<len;i++)
            {
                if(i>0&&dp[i-1]>0)
                {
                    dp[i]=max(dp[i-1]+arr[i],dp[i]);
                }
                else
                {
                    dp[i]=max(dp[i],arr[i]);
                }
                if(dp[i]>ans)
                {
                    ans=dp[i];
                }
                num+=arr[i];
            }
            if(k>1&&num>0)
            {
                int sum1=0;
                int ans1=0;
                int sum2=0;
                int ans2=0;
                for(i=len-1;i>=0;i--)
                {
                    sum1+=arr[i];
                    if(sum1>ans1)
                    {
                        ans1=sum1;
                    }
                }
                for(i=0;i<len;i++)
                {
                    sum2+=arr[i];
                    if(sum2>ans2)
                    {
                        ans2=sum2;
                    }
                }
                long long int res=(long long int)num*(k-2)+ans1+ans2;
                return res%(1000000007);
            }
            else if(k>1)
            {
                for(i=len;i<2*len;i++)
                {
                    arr.push_back(arr[i-len]);
                    if(i>0&&dp[i-1]>0)
                    {
                        dp[i]=max(dp[i-1]+arr[i],dp[i]);
                    }
                    else
                    {
                        dp[i]=max(dp[i],arr[i]);
                    }
                    if(dp[i]>ans)
                    {
                        ans=dp[i];
                    }
                }
                return ans;
            }
            else
            {
                return ans;
            }
        }
    };