题目如下:
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).
解题思路: 本题如果只要求求出三段子数组的和的最大值, 那会简单很多. 记 total[i] 为 arr[i:i+k] 段的和, dp_left_max[i] 为 nums[:i] 区间内长度为 k 的子数组的和的最大值, dp_right_max[i] 为 nums[i:len(nums)] 区间内长度为 k 的子数组的和的最大值, 很显然如果中间段的子数组的下标为 k, 那么可以得到三段和的最大长度的表达: total[i] + dp_left_max[i-k] + dp_right_max[i+k] . 只要遍历数组 arr, 即可求出最大值. 求出后就是计算出左边以及右边最大值出现时的最小下标, 这个可以通过二分查找实现.
代码如下:
- class Solution(object):
- def maxSumOfThreeSubarrays(self, nums, k):
- """
- :type nums: List[int]
- :type k: int
- :rtype: List[int]
- """
- count = sum(nums[:k])
- total = [count]
- total_inx = {}
- total_inx[count] = [0]
- dp_left_max = [count]
- dp_left_max_count = count
- for i in range(k, len(nums)):
- count -= nums[i - k]
- count += nums[i]
- total += [count]
- total_inx[count] = total_inx.setdefault(count,[]) + [i-k + 1]
- dp_left_max_count = max(dp_left_max_count,count)
- dp_left_max.append(dp_left_max_count)
- reverse_num = nums[::-1]
- count = sum(reverse_num[:k])
- dp_right_max = [count]
- dp_right_max_count = count
- for i in range(k, len(reverse_num)):
- count -= reverse_num[i - k]
- count += reverse_num[i]
- dp_right_max_count = max(dp_right_max_count,count)
- dp_right_max.insert(0,dp_right_max_count)
- #print total
- #print total_inx
- #print dp_left_max
- #print dp_right_max
- max_sum = -float('inf')
- mid_inx = 0
- left_val = 0
- right_val = 0
- for i in range(k,len(nums)-k-k+1):
- count = total[i] + dp_left_max[i-k] + dp_right_max[i+k]
- if count> max_sum:
- mid_inx = i
- left_val = dp_left_max[i-k]
- right_val = dp_right_max[i+k]
- max_sum = count
- #print left_val,mid_inx,right_val
- left_inx = total_inx[left_val][0]
- import bisect
- right_inx = bisect.bisect_left(total_inx[right_val],mid_inx+k)
- return [left_inx,mid_inx,total_inx[right_val][right_inx]]
来源: http://www.bubuko.com/infodetail-3221995.html