Create split-array-largest-sum.py

kamyu104 · web-flow · commit 0795585e9efb · 2016-10-05T23:43:41.000+08:00
diff --git a/Python/split-array-largest-sum.py b/Python/split-array-largest-sum.py
@@ -0,0 +1,52 @@
+# Time:  O(nlogs), s is the sum of nums
+# Space: O(1)
+
+# 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:
+# Given m satisfies the following constraint: 1 <= m <= length(nums) <= 14,000.
+#
+# 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.
+
+class Solution(object):
+    def splitArray(self, nums, m):
+        """
+        :type nums: List[int]
+        :type m: int
+        :rtype: int
+        """
+        def canSplit(nums, m, s):
+            cnt, curr_sum = 1, 0
+            for num in nums:
+                curr_sum += num
+                if curr_sum > s:
+                    curr_sum = num
+                    cnt += 1
+            return cnt <= m
+
+        left, right = 0, 0
+        for num in nums:
+            left = max(left, num)
+            right += num
+
+        while left <= right:
+            mid = left + (right - left) / 2;
+            if canSplit(nums, m, mid):
+                right = mid - 1
+            else:
+                left = mid + 1
+        return left
