資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在 C++ 中找到最大和嚴格遞增子陣列
假設我們有一個包含 n 個整數的陣列。找到和最大的嚴格遞增子陣列。所以如果陣列像 [1, 2, 3, 2, 5, 1, 7]，則和為 8。在這個陣列中有三個嚴格遞增的子陣列，分別是 {1, 2, 3}、{2, 5} 和 {1, 7}。和最大的子陣列是 {1, 7}
要解決這個問題，我們必須跟蹤最大和和當前和。對於每個元素 arr[i]，如果它大於 arr[i – 1]，那麼我們將它新增到當前和中，否則 arr[i] 是另一個子陣列的起點。所以我們應該將當前和更新為陣列。在更新當前和之前，我們將根據需要更新最大和。
示例
#include<iostream>
using namespace std;
int maximum(int a, int b){
return (a>b)?a:b;
}
int maximum_sum_incr_subarr(int array[] , int n) {
int max_sum = 0;
int current_sum = array[0] ;
for (int i=1; i<n ; i++ ) {
if (array[i-1] < array[i])
current_sum = current_sum + array[i];
else {
max_sum = maximum(max_sum, current_sum);
current_sum = array[i];
}
}
return max(max_sum, current_sum);
}
int main() {
int arr[] = {1, 2, 3, 2, 5, 1, 7};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Maximum sum : " << maximum_sum_incr_subarr(arr , n);
}輸出
Maximum sum : 8
更新日期：18-12-2019
210 次瀏覽
廣告