給定一個無序數(shù)組arr, 其中元素可正, 可負(fù), 可0, 給定一個整數(shù)k. 求arr所有的子數(shù)組中累加和小于或等于k的最長子數(shù)組長度.
例如:
arr[] = {3, -2, -4, 0, 6}, k=2
相加和小于或等于-2的最長子數(shù)組為[3, -2, -4, 0],所有結(jié)果返回4.
算法分析
基本思想是, 分別求以數(shù)組每個元素結(jié)尾的子數(shù)組中, 累加和小于或等于k的最長子數(shù)組長度, 其中最長的那個子數(shù)組的長度就是所求的結(jié)果.
關(guān)鍵是如何高效地確定, 以每個元素結(jié)尾的, 滿足要求的最長子數(shù)組長度.
例如如果要求以元素 arr[30]結(jié)尾, 累加和小于等于k的最長子數(shù)組長度.
- arr[0..30]子數(shù)組和為sum(30)
- 如果在0和30之間有某個下標(biāo)j=10, arr[0..10]子數(shù)組和為sum(10)
- 有 sum(30) - sum(10) <= k, 并且10是第一個下標(biāo)滿這個條件
- 那么 arr[11..30]即是以arr[30]結(jié)尾的, 子數(shù)組和小于等于k的最長子數(shù)組.
為了更高效地為尋找以每一個元素結(jié)尾的滿足條件的最長子數(shù)組, 需要生成輔助數(shù)組.
該輔助數(shù)組為以第一個元素開始到目標(biāo)元素結(jié)尾的子數(shù)組的和.
輔助數(shù)組的第一個元素為0, 表示子數(shù)組為空時, 累加和為0.
舉一個栗子, 對于數(shù)組 [1, 2, -1, 5, -2]
生成的輔助數(shù)組為 [0, 1, 3, 2, 7, 5].
這樣的輔助數(shù)組使用起來還不夠高效, 因為每一次查找時, 我們都要遍歷一次這個數(shù)組, 找到第一個大于 sum - k的元素的下標(biāo). 所以我們對輔助數(shù)組做修訂.
修訂后的輔助數(shù)組是 [0, 1, 3, 3, 7, 7]. 做這個變動, 是因為我們需要尋找的, 是最早滿足累加和大于或等于sum - k的元素下標(biāo), 如果在這個元素后面的累加和比sum - k,可以完全忽略. 這里我們將2變?yōu)?, 5變?yōu)?, 是為了讓這個輔助數(shù)組有序, 從而可以用二分查找的方式查找第一個大于等于 sum - k的元素.
實現(xiàn)
class Solution
{
public:
int maxSubarraySumLessOrEqualK(std::vector<int>& nums, int target)
{
if (nums.size() == 0)
{
return 0;
}
std::vector<int> sumArray;
int sum = 0;
int maxLen = 0;
sumArray.push_back(sum);
for (int cur = 0; cur < nums.size(); ++cur)
{
sum += nums[cur];
int start = binarySearch(sumArray, sum - target);
int len = start == -1 ? 0 : cur - start + 1;
maxLen = std::max(maxLen, len);
int toPush = std::max(sum, sumArray.back());
sumArray.push_back(toPush);
}
return maxLen;
}
private:
// find element >= key
int binarySearch(std::vector<int> sumArray, int key)
{
int left = 0;
int right= sumArray.size() - 1;
int mid = -1;
while (left <= right)
{
mid = (right + left) / 2;
if (sumArray[mid] >= key)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return left < sumArray.size() ? left : -1;
}
};
