LC.P1043[分隔数组以得到最大和]

方法一：动态规划(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int[] arr;
    int k;

    public int maxSumAfterPartitioning(int[] arr, int k) {
        this.arr = arr;
        this.k = k;
        return dfs(arr.length - 1);
    }

    private int dfs(int i) {
        int ans = 0, max = 0;
        for (int j = i; j > i - k && j >= 0; --j) {
            max = Math.max(max, arr[j]);
            ans = Math.max(ans, dfs(j - 1) + (i - j + 1) * max);
        }
        return ans;
    }
}
  • 时间复杂度：$O(k^n)$，其中$n$为$arr$的长度，近似可看做一棵高度为$n$的$k$叉树。
  • 空间复杂度：$O(n)$

方法二：动态规划+记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    int[] arr;
    int k;
    Map<Integer, Integer> cache;

    public int maxSumAfterPartitioning(int[] arr, int k) {
        this.arr = arr;
        this.k = k;
        cache = new HashMap<>();
        return dfs(arr.length - 1);
    }

    private int dfs(int i) {
        if (cache.containsKey(i)) return cache.get(i);
        int ans = 0, max = 0;
        for (int j = i; j > i - k && j >= 0; --j) {
            max = Math.max(max, arr[j]);
            ans = Math.max(ans, dfs(j - 1) + (i - j + 1) * max);
        }
        cache.put(i, ans);
        return ans;
    }
}

数组实现(速度更快)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    int[] arr;
    int k;
    int[] cache;

    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        this.arr = arr;
        this.k = k;
        cache = new int[n];
        return dfs(n - 1);
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        if (cache[i] != 0) return cache[i];
        int ans = 0, max = 0;
        for (int j = i; j > i - k && j >= 0; --j) {
            max = Math.max(max, arr[j]);
            ans = Math.max(ans, dfs(j - 1) + (i - j + 1) * max);
        }
        return cache[i] = ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func maxSumAfterPartitioning(arr []int, k int) int {
    n := len(arr)
    memo := make([]int, n)
    for i := range memo {
        memo[i] = -1 // -1 表示还没有计算过
    }
    var dfs func(int) int
    dfs = func(i int) (res int) {
        if i < 0 {
            return
        }
        if memo[i] != -1 { // 之前计算过了
            return memo[i]
        }
        for j, mx := i, 0; j > i-k && j >= 0; j-- {
            mx = max(mx, arr[j]) // 一边枚举 j，一边计算子数组的最大值
            res = max(res, dfs(j-1)+(i-j+1)*mx)
        }
        memo[i] = res // 记忆化
        return
    }
    return dfs(n - 1)
}

func max(a, b int) int { 
    if a < b { 
        return b 
    }
    return a 
}
  • 时间复杂度：$O(nk)$
  • 空间复杂度：$O(n)$

方法三：递推

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] f = new int[n + 1];
        for (int i = 0; i < n; ++i)
            for (int j = i, max = 0; j > i - k && j >= 0; --j) {
                max = Math.max(max, arr[j]);
                f[i + 1] = Math.max(f[i + 1], f[j] + (i - j + 1) * max);
            }
        return f[n];
    }
}
  • 时间复杂度：$O(nk)$
  • 空间复杂度：$O(n)$