資訊專欄INFORMATION COLUMN
摘要：題目鏈接枚舉所有可能的，找最小的那個(gè)，二分枚舉優(yōu)化復(fù)雜度，因?yàn)閿?shù)組不含負(fù)數(shù)，根據(jù)是否滿足條件可以二分結(jié)果。注意由于不含負(fù)數(shù)，并且，相當(dāng)于一條遞增，一條遞減的線找交點(diǎn)，極端情況沒(méi)有交點(diǎn)結(jié)果出現(xiàn)在兩端，所以依然可以找。
410. Split Array Largest Sum
題目鏈接：https://leetcode.com/problems...
枚舉所有可能的largest sum，找最小的那個(gè)，二分枚舉優(yōu)化復(fù)雜度，因?yàn)閿?shù)組不含負(fù)數(shù)，根據(jù)largest sum是否滿足條件可以二分結(jié)果。largest sum的范圍是(sum(nums)/m, sum(nums))，找當(dāng)前l(fā)argest sum是否存在，判斷存在的標(biāo)準(zhǔn)是：掃一遍array，看實(shí)現(xiàn)每個(gè)subarray的sum都<=當(dāng)前l(fā)argest sum的時(shí)候subarray的數(shù)量是否小于等于mm，注意求數(shù)組sum要用long，防止溢出。
public class Solution {
public int splitArray(int[] nums, int m) {
long sum = 0;
for(int num : nums) sum += num;
// binary search, find the minimum valid sum
long l = sum / m;
long r = sum;
while(l < r) {
long mid = l + (r - l) / 2;
boolean valid = isValidSplit(nums, m, mid);
if(valid) r = mid;
else l = mid + 1;
}
return (int) l;
}
private boolean isValidSplit(int[] nums, int m, long sum) {
int i = 0, n = nums.length;
// count the minimum number of split
int count = 0;
// prev sum
long prev = 0;
// loop invariant: prev = 0, count = minimum splits so far
while(i < n) {
if(nums[i] > sum) return false;
while(i < n && prev + nums[i] <= sum) {
prev += nums[i++];
}
count++;
if(count > m) return false;
prev = 0;
}
return count <= m;
}
}
還有一種dp的做法：
https://discuss.leetcode.com/...
dp的subproblem是：
dp[i][j]: split nums[0:i] into j parts,
dp的方程是：
dp[i][j] = min{ max{dp[k][j-1], sum(nums[k+1:i+1])} },
每個(gè)subproblem都遍歷一遍可能的k，選擇出最小的結(jié)果。注意由于array不含負(fù)數(shù)，dp[k-1] <= dp[k] 并且sum(nums[k:i+1]) >= sum(nums[k+1:i+1])，相當(dāng)于一條遞增，一條遞減的線找交點(diǎn)，極端情況沒(méi)有交點(diǎn)結(jié)果出現(xiàn)在兩端，所以依然可以binary search找dp[k] == sum(nums[k+1:i+1])。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/76393.html
摘要：在這里，邊界被設(shè)置為該數(shù)組中可以得到的子數(shù)組元素和的最小值和最大值。在確定了數(shù)組元素和的上界和下界之后，就需要找出一種方法，來(lái)不斷壓縮區(qū)間直到最后一種?？梢允褂弥虚g位置作為數(shù)組元素和的邊界，即假設(shè)所有的連續(xù)數(shù)組的和都不會(huì)超過(guò)值。 題目要求 Given an array which consists of non-negative integers and an integer m, y...
Problem Find the contiguous subarray within an array (containing at least one number) which has the largest sum. Example For example, given the array [-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray [4...
摘要：最新更新請(qǐng)見(jiàn)原題鏈接動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路這是一道非常典型的動(dòng)態(tài)規(guī)劃題，為了求整個(gè)字符串最大的子序列和，我們將先求較小的字符串的最大子序列和。而最大子序列和的算法和上個(gè)解法還是一樣的。 Maximum Subarray 最新更新請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...
摘要：如果單開元素加和更大判斷前面的子數(shù)組和是不是小于。此元素就成為了子數(shù)組的第一個(gè)元素。每次操作都要判斷，當(dāng)前是否是最大值，更新值。 題目詳情 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given t...
摘要：我們可以分別得出這三種情況下的最大子數(shù)列和，并比較得出最大的那個(gè)。我們只需要考慮左子列的最大和以及跨越了左右的中子列的最大值。 題目要求 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given ...
閱讀 3162·2021-11-22 09:34
閱讀 659·2021-11-22 09:34
閱讀 2518·2021-10-08 10:18
閱讀 3447·2021-09-22 15:57
閱讀 2699·2021-09-22 15:25
閱讀 2507·2019-08-30 15:54
閱讀 2259·2019-08-30 15:44
閱讀 1856·2019-08-29 11:18
