資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式中，最大子陣列大小，使得所有該大小的子陣列的和都小於k
在這個問題中，我們得到一個包含n個正整數的陣列arr[]和一個整數k。我們的任務是建立一個程式來查詢最大子陣列大小，使得所有該大小的子陣列的和都小於k。
問題描述 - 我們需要找到最大子陣列的大小，使得由陣列元素建立的所有該大小的子陣列的元素之和都小於或等於k。
讓我們舉個例子來理解這個問題：
輸入
arr[n] = {4, 1, 3, 2}, k = 9輸出
3
解釋
所有大小為3的子陣列及其和：
{4, 1, 3} = 8
{1, 3, 2} = 6
The sum of all subarrays of size 3 is less than or equal to k.解決方案
解決這個問題的一個簡單方法是找到大小可能大於k的子陣列。為此，我們將建立一個字首和，表示直到給定索引的元素之和。對於此字首和，我們將找到小於k的最大結果，其索引將是我們的結果。在這裡，我們使用了這樣一個事實：如果對於任何大小，字首和都大於k，而其餘的和都小於k，那麼所有大小為-1的子陣列的和都小於k。
示例
程式說明了我們解決方案的工作原理：
#include<iostream>
using namespace std;
int calcSubArraySize(int arr[], int n, int k){
int prefixSum[n + 1];
prefixSum[0] = 0;
for (int i = 0; i < n; i++)
prefixSum[i + 1] = prefixSum[i] + arr[i];
// Searching size
int maxLen = −1;
int start = 1, end = n;
int mid, i;
while (start <= end){
int mid = (start + end) / 2;
for (i = mid; i <= n; i++){
if (prefixSum[i] − prefixSum[i − mid] > k)
break;
}
if (i == n + 1){
start = mid + 1;
maxLen = mid;
}
else
end = mid − 1;
}
return maxLen;
}
int main(){
int arr[] = {4, 1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 9;
cout<<"The maximum subarray size, such that all subarrays of that
size have sum less than k is "<<calcSubArraySize(arr, n, k);
return 0;
}輸出
這種方法效率很高，但可以採用更好的方法來解決這個問題：
在這種方法中，我們將使用滑動視窗法來查詢子陣列的和。首先取所有元素，我們將找到和保持在k以上的值的長度。然後返回長度-1，即所有子陣列的和都小於或等於0的最大子陣列大小。
示例
程式說明了我們解決方案的工作原理：
#include <iostream>
using namespace std;
int calcSubArraySizeSW(int arr[], int n, int k){
int maxLen = n;
int subArraySum = 0;
int start = 0;
for (int end = 0; end < n; end++){
subArraySum += arr[end];
while (subArraySum > k) {
subArraySum −= arr[start];
start++;
maxLen = min(maxLen, end − start + 1);
if (subArraySum == 0)
break;
}
if (subArraySum == 0) {
maxLen = −1;
break;
}
}
return maxLen;
}
int main(){
int arr[] = { 4, 1, 3, 2, 6 };
int k = 12;
int n = sizeof(arr)/ sizeof(arr[0]);
cout<<"The maximum subarray size, such that all subarrays of that
size have sum less than k is "<<calcSubArraySizeSW(arr, n, k);
return 0;
}輸出
The maximum subarray size, such that all subarrays of that size have sum less than k is 4
更新於：2020年12月9日
瀏覽量 188
廣告