题目描述：

LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Note:

• nums.length will be between 1 and 20000.
• nums[i] will be between 1 and 65535.
• k will be between 1 and floor(nums.length / 3).

题目大意：

给定正整数数组nums，计算其中不想交的3段子数组的最大和。每段子数组的长度为k。

解题思路：

预处理，时间复杂度O(n)

构造K项和数组sums，sums[i] = sum(nums[i - k + 1 .. i])

从左向右构造K项和最大值及其下标数组maxa，其元素记为va, ia

从右向左构造K项和最大值及其下标数组maxb，其元素记为vb, ib

在[k, nsize - k)范围内枚举中段子数组的起点x

则3段子数组和 = sums[x] + va + vb

Python代码：

class Solution(object):
    def maxSumOfThreeSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        size = len(nums)
        nsize = size - k + 1
        sums = [0] * nsize
        maxa = [0] * nsize
        maxb = [0] * nsize
        total = 0
        for x in range(size):
            total += nums[x]
            if x >= k - 1:
                sums[x - k + 1] = total
                total -= nums[x - k + 1]
        maxn, maxi = 0, 0
        for x in range(nsize):
            if sums[x] > maxn:
                maxn, maxi = sums[x], x
            maxa[x] = (maxn, maxi)
        maxn, maxi = 0, nsize - 1
        for x in range(nsize - 1, -1, -1):
            if sums[x] > maxn:
                maxn, maxi = sums[x], x
            maxb[x] = (maxn, maxi)
        ansn, ansi = 0, None
        for x in range(k, nsize - k):
            va, ia = maxa[x - k]
            vb, ib = maxb[x + k]
            if sums[x] + va + vb > ansn:
                ansn = sums[x] + va + vb
                ansi = [ia, x, ib]
        return ansi

 

本文链接：http://bookshadow.com/weblog/2017/10/01/leetcode-maximum-sum-of-3-non-overlapping-subarrays/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码