資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中小於等於給定和的最大子陣列和
在這個問題中，我們給定一個數組和一個和。我們的任務是建立一個程式，在 C++ 中找到和不大於給定和的最大子陣列和。
我們必須找到長度小於等於 n 且和不大於給定和的任何長度的子陣列。
讓我們舉個例子來理解這個問題：
輸入 − array = {3, 5, 1, 8, 2, 9}, sum = 25
輸出 − 25
解釋 − 和不大於 25 的子陣列是 {5, 1, 8, 2, 9}
找到最大子陣列和的一種簡單方法是遍歷陣列並找到所有子陣列的和，然後找到最接近或等於的和。但是這種方法的時間複雜度為 O(n*n)，因為需要兩個迴圈。
解決這個問題的一個更有效的方法是使用滑動視窗方法。在這種方法中，我們將當前和與最大和進行比較，並根據比較結果向視窗新增或減去元素。
示例
程式說明了解決方案的工作原理：
#include <iostream>
using namespace std;
int findMax(int a, int b){
if(a>b)
return a;
return b;
}
int maxSumsubarray(int arr[], int n, int maxSum){
int sum = arr[0], overallMax = 0, start = 0;
for (int i = 1; i < n; i++) {
if (sum <= maxSum)
overallMax = findMax(overallMax, sum);
while (sum + arr[i] > maxSum && start < i) {
sum -= arr[start];
start++;
}
sum += arr[i];
}
if (sum <= maxSum)
overallMax = findMax(overallMax, sum);
return overallMax;
}
int main(){
int arr[] = {3, 1, 4, 7, 2, 9, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 20;
cout<<"The maximum sum of subarray with sum less than or equal to "<<sum<<" is "<<maxSumsubarray(arr, n, sum);
return 0;
}輸出
The maximum sum of subarray with sum less than or equal to 20 is 18
更新於：2020年6月3日
612 次瀏覽
廣告