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

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

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

思路分析

解法一：动态规划（推荐）

核心思路：

dp[i] 表示前 i 个元素分割后的最大和。

枚举最后一段长度 len（1..k），维护该段最大值 maxVal。

转移：dp[i] = max(dp[i-len] + maxVal * len)。

复杂度分析：

时间复杂度：O(nk)，其中 n 表示数组长度。

空间复杂度：O(n)。

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int maxVal = 0;
            for (int len = 1; len <= k && i - len >= 0; len++) {
                maxVal = Math.max(maxVal, arr[i - len]);
                dp[i] = Math.max(dp[i], dp[i - len] + maxVal * len);
            }
        }
        return dp[n];
    }
}

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

    for i := 1; i <= n; i++ {
        maxVal := 0
        for l := 1; l <= k && i-l >= 0; l++ {
            if arr[i-l] > maxVal {
                maxVal = arr[i-l]
            }
            val := dp[i-l] + maxVal*l
            if val > dp[i] {
                dp[i] = val
            }
        }
    }
    return dp[n]
}

相似题目

题目	难度	考察点
198. 打家劫舍	中等	动态规划
300. 最长递增子序列	中等	DP
813. 最大平均值和的分组	中等	DP
1043. 分隔数组以得到最大和	中等	DP
139. 单词拆分	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/92396509