410. Split Array Largest Sum

• 410. Split Array Largest Sum
  • Description
  • Intuition
    • Dp
    • Binary Search
  • Pitfall
  • Solution
  • Reference

Description

Here

Intuition

这题思路超多，可以用dp或者binary Search做

Dp

dp[m][n] 可以表示为max sum of subarry whose size m and using n

反过来也可以

• Dp Solution 1
• Dp Solution 2

Binary Search

Value 上面做Binary Search. 答案肯定是[max value in array, Sum of array], 所以binary search value

如果greedy 能够分成m组使得每一组subarray的sum都小于等于midValue，那么这个midValue选的 可能 太大

Pitfall

Solution

Binary Search Solution

Reference

• Leetcode Discussion