In this Leetcode Split Array Largest Sum problem solution, You are given an array nums 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.
Problem solution in Python.
class Solution: def splitArray(self, nums: List[int], m: int) -> int: dp = [[float("inf") for _ in range(len(nums))] for _ in range(m)] dp[0][0] = nums[0] for j in range(1, len(nums)): dp[0][j] = dp[0][j-1] + nums[j] for i in range(1,m): for j in range(i, len(nums)): dp[i][j] = min([max(dp[i-1][k],dp[0][j]-dp[0][k]) for k in range(i-1, j)]) return dp[-1][-1]
Problem solution in Java.
class Solution { public int splitArray(int[] nums, int m) { int low = IntStream.of(nums).max().orElse(0); int high = IntStream.of(nums).sum(); while (low < high) { int mid = low + (high - low) / 2; if (split(nums, mid) > m) { low = mid + 1; } else { high = mid; } } return low; } private int split(int[] nums, int sum) { int ret = 1; int currentSum = 0; for (int i = 0; i < nums.length; i++) { if (currentSum + nums[i] > sum) { ret++; currentSum = 0; } currentSum += nums[i]; } return ret; } }
Problem solution in C++.
bool can_split(vector<int> &nums,int m,long long int sum) { long long int cnt=1,cnt_sum=0; for (int i = 0; i <nums.size() ; ++i) { cnt_sum+=nums[i]; if(cnt_sum>sum) { cnt_sum=nums[i]; ++cnt; if (cnt>m) return false; } } return true; } int splitArray(vector<int>& nums, int m) { long long left=*max_element(nums.begin(),nums.end()); long long right=accumulate(nums.begin(),nums.end(),0ll); while(left<right) { long long mid=(left+right)>>1; if(can_split(nums,m,mid)) right=mid; else left=mid+1; } return left; }
0 Comments