leetcode-1043-Partition-Array-for-Maximum-Sum

发表于   |  

描述

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

1
2
3
Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

Note:

  1. 1 <= K <= A.length <= 500
  2. 0 <= A[i] <= 10^6

分析

分割数组，然后每个数组中的元素变成该数组中的最大值，找到能够得到的最大和。

动态规划题目，转移方程可以这样推导，用 result[i] 表示划分了前 i 个数字产生的最大和，初始时 result[0] 为0，考虑第 i 个数字是，与之前 k 个数字组成子数组，取 result[i] 与 result[i-j] + current_max 的最大值，其中 current_max 是 A[i-j] 到 A[i-1] 之间的最大值。

解决方案1(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxSumAfterPartitioning(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        result = [-1] * (len(A)+1)
        result[0] = 0
        for i in xrange(1, len(A)+1):
            current_max = -1
            j = 1
            while j <= K and i-j >= 0:
                current_max = max(current_max, A[i-j])
                result[i] = max(result[i], result[i-j] + current_max*j)
                j = j+1
        return result[len(A)]

题目来源