leetcode 410. Split Array Largest Sum - 淡然坊 - CSDN博客

leetcode 410. Split Array Largest Sum - 淡然坊 - CSDN博客

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

Input:  nums = [7,2,5,10,8]  m = 2    Output:  18    Explanation:  There are four ways to split nums into two subarrays.  The best way is to split it into [7,2,5] and [10,8],  where the largest sum among the two subarrays is only 18.

这道题很明显又是一道递归 with memo 或者 DP 的题。

这道题又一次印证了 map 没有 int[][]数组 快的结论！因为我使用 HashMap<Integer,HashMap<Integer,Integer> 华丽丽地TLE了，但是改成 int[][] 就AC了。

我的思路是：int[row][column] ：row存储了当前数组的开始索引 left，column 存储了当前的 m。因此 memo[i][j] 就是：从 i 开始的数组要被划分为 j 个子数组时的结果值。

Read full article from leetcode 410. Split Array Largest Sum - 淡然坊 - CSDN博客