esc to dismiss

1043. 分隔数组以得到最大和

题目

给你一个整数数组 arr,请你将该数组分隔为长度最多为 k 的一些(连续)子数组。分隔完成后,每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。

注意,原数组和分隔后的数组对应顺序应当一致,也就是说,你只能选择分隔数组的位置而不能调整数组中的顺序。

示例 1:

输入:arr = [1,15,7,9,2,5,10], k = 3

输出:84

解释:

因为 k=3 可以分隔成 [1,15,7] [9] [2,5,10],结果为 [15,15,15,9,10,10,10],和为 84,是该数组所有分隔变换后元素总和最大的。

若是分隔成 [1] [15,7,9] [2,5,10],结果就是 [1, 15, 15, 15, 10, 10, 10] 但这种分隔方式的元素总和(76)小于上一种。

示例 2:

输入:arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4

输出:83

示例 3:

输入:arr = [1], k = 1

输出:1

解体思路

本题的算法是 动态规划

我们针对例子这样来思考,对于 a = [[1,15,7,9,2,5,10], k = 3 ,我们来推导状态转移方程。从数组第0个小标开始向右推导,每个阶段子数组最大和为状态变量 f(n) [动态规划]]

f(0)  1
f(1)  30  // 子数组内最大数*子数组长度 15*2
f(2)  45
// 第4个元素就要决策了
f(3)  54  // max{ f(0)+sum{a[1],a[2],a[3]}, f(1)+sum{a[2],a[3]}, f(2)+sum{a[3]} }
f(4)  63  // max{ f(1)+sum{a[2],a[3],a[4]}, f(2)+sum{a[3],a[4]}, f(3)+sum{a[4]} }
......

这样我们的状态转移方程就出来:

f(n) = max{ f(n-k)+sum{a[n-k+1],...a[n]}, ..., f(n-1)+sum{a[n]} }

考虑条件和边界值,代码就可以写出来了。

参考代码:

func subArraySum(arr []int) int {
    max := 0
    for _, n := range arr {
        if n > max {
            max = n
        }
    }
    return max * len(arr)
}

func maxSumAfterPartitioning(arr []int, k int) int {
    size := len(arr)
    dp := make([]int, size, size)

    for i := 0; i < k; i++ {
        dp[i] = subArraySum(arr[:i+1])
    }

    for i := k; i < size; i++ {
        max := -1
        for j := k; j > 0; j-- {
            sum := dp[i-j] + subArraySum(arr[i-j+1:i+1])
            if sum > max {
                max = sum
            }
        }
        dp[i] = max
    }
    return dp[size-1]
}

经验教训

...

x