【leetcode】1191. K-Concatenation Maximum Sum

题目如下：

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 = 3 then 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:
Input: arr = [1,2], k = 3

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

Output: 2
Example 3:
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. 0;

2. arr[i] ;

3. sum(arr) * k ;

4. sum(arr[i:j]) ，这种场景其实就是求最大字段和；

5.sum(arr[i:len(arr)]) + sum(arr[0:j]) ，需要满足k>1。这种场景是第一个arr的尾部的最大值加上第二个arr头部的最大值；

6.sum(arr[i:len(arr)]) + sum(arr[0:j]) + (k-2） * sum(arr) ，需要满足k>2。这种场景是第一个arr的尾部的最大值加上最后一个arr头部的最大值。

代码如下：

class Solution(object):

    def kConcatenationMaxSum(self, arr, k):

        """

        :type arr: List[int]

        :type k: int

        :rtype: int

        """

        res = 0

        left_max = []

        amount = 0

        min_sub_arr_sum = 0

        max_arr_sum = 0

        for i in arr:

            res = max(i,res)  # single item

            amount += i

            min_sub_arr_sum = min(min_sub_arr_sum, amount)

            max_arr_sum = max(max_arr_sum,amount)

            res = max(res, amount - min_sub_arr_sum)

            left_max.append(max_arr_sum)

        total_sum = amount

        res = max(res,total_sum*k) # all

        amount = 0

        max_sub_arr_sum = -float('inf')

        for i in range(len(arr) - 1, -1, -1):

            amount += arr[i]

            max_sub_arr_sum = max(max_sub_arr_sum,amount)

            res = max(res,max_sub_arr_sum + left_max[-1])

            if k > 2:

                res = max(res,max_sub_arr_sum + left_max[-1] + (k-2)*total_sum)

        return res % (10 ** 9 + 7)

巴特西

【leetcode】1191. K-Concatenation Maximum Sum

最新文章

热门文章