Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

410. Split Array Largest Sum

Time: $O(mn^2)$

Space: $O(mn)$

			


class Solution {
 public:
  int splitArray(vector<int>& nums, int m) {
    const int n = nums.size();
    // dp[i][k] := min of largest sum to split first i nums into k groups
    dp.resize(n + 1, vector<int>(m + 1, INT_MAX));
    prefix.resize(n + 1);

    partial_sum(begin(nums), end(nums), begin(prefix) + 1);
    return splitArray(nums, n, m);
  }

 private:
  vector<vector<int>> dp;
  vector<int> prefix;

  int splitArray(const vector<int>& nums, int i, int k) {
    if (k == 1)
      return prefix[i];
    if (dp[i][k] < INT_MAX)
      return dp[i][k];

    // Try all possible partitions
    for (int j = k - 1; j < i; ++j)
      dp[i][k] =
          min(dp[i][k], max(splitArray(nums, j, k - 1), prefix[i] - prefix[j]));

    return dp[i][k];
  }
};




			


class Solution {
  public int splitArray(int[] nums, int m) {
    final int n = nums.length;
    // dp[i][k] := min of largest sum to split first i nums into k groups
    dp = new int[n + 1][m + 1];
    prefix = new int[n + 1];

    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));

    for (int i = 0; i < n; ++i)
      prefix[i + 1] = nums[i] + prefix[i];

    return splitArray(nums, n, m);
  }

  private int[][] dp;
  private int[] prefix;

  private int splitArray(int[] nums, int i, int k) {
    if (k == 1)
      return prefix[i];
    if (dp[i][k] < Integer.MAX_VALUE)
      return dp[i][k];

    // Try all possible partitions
    for (int j = k - 1; j < i; ++j)
      dp[i][k] = Math.min(dp[i][k], Math.max(splitArray(nums, j, k - 1), prefix[i] - prefix[j]));

    return dp[i][k];
  }
}




			


class Solution:
  def splitArray(self, nums: List[int], m: int) -> int:
    n = len(nums)
    prefix = [0] + list(itertools.accumulate(nums))

    # Dp(i, k) := min of largest sum to split first i nums into k groups
    @functools.lru_cache(None)
    def dp(i: int, k: int) -> int:
      if k == 1:
        return prefix[i]

      ans = math.inf

      # Try all possible partitions
      for j in range(k - 1, i):
        ans = min(ans, max(dp(j, k - 1), prefix[i] - prefix[j]))

      return ans

    return dp(n, m)