leetcode 1191

问题

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 = 3then 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:

1
2
Input: arr = [1,2], k = 3
Output: 9

Example 2:

1
2
Input: arr = [1,-2,1], k = 5
Output: 2

Example 3:

1
2
Input: arr = [-1,-2], k = 7
Output: 0

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= k <= 10^5
  • -10^4 <= arr[i] <= 10^4

分析

三种情况：

  1. arr中的最大子序列
  2. arr的最大前缀和加上arr的最大后坠和
  3. arr的最大前缀和加上arr的最大后坠和，再加上$sum(arr)*(k-1)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int n = arr.size();
        int sum = 0, subArrMax = 0, dp = 0;
        int suffixMax = 0, suffixCur = 0;
        for (int i = 0; i < n; ++i) {
            sum += arr[i];
            suffixCur = suffixCur + arr[i];
            suffixMax = max(suffixMax, suffixCur);
            dp = max(arr[i], dp+arr[i]);
            subArrMax = max(subArrMax, dp);
        }
        
        int prefixMax = 0, prefixCur = 0;
        for (int i = n-1; i >= 0; --i) {
            prefixCur = prefixCur + arr[i];
            prefixMax = max(prefixMax, prefixCur);
        }

        if (k == 1)
            return subArrMax;
        if (sum > 0) {
            long long t1 = subArrMax;
            long long t2 = (long long)sum*(k-2) + suffixMax + prefixMax;
            return (t1 > t2? t1: t2)%1000000007;
        }
        long long t1 = subArrMax;
        long long t2 = suffixMax+prefixMax;
        return (t1>t2? t1: t2)%1000000007;
    }
};