資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚研究
法律研究使用 C++ 中的字首和以 O(n) 計算最大子陣列和
問題陳述
給定一個正整數和負整數陣列，找出該陣列中的最大子陣列和
示例
如果輸入陣列為 {-12, -5, 4, -1, -7, 1, 8, -3}，則輸出為 9
演算法
計算輸入陣列的字首和。
初始化 - min_prefix_sum = 0，res = - 無窮大
維護從 i = 0 到 n 的迴圈。（n 是輸入陣列的大小）。
cand = prefix_sum[i] - mini
如果 cand 大於 res（目前為止的最大子陣列和），則按 cand 更新 res。
如果 prefix_sum[i] 小於 min_prefix_sum（目前為止的最小字首和），則按 prefix_sum[i] 更新 min_prefix_sum。
返回 res
示例
#include <bits/stdc++.h>
using namespace std;
int maximumSumSubarray(int *arr, int n){
int minPrefixSum = 0;
int res = numeric_limits<int>::min();
int prefixSum[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
for (int i = 0; i < n; i++) {
res = max(res, prefixSum[i] - minPrefixSum);
minPrefixSum = min(minPrefixSum, prefixSum[i]);
}
return res;
}
int main(){
int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Result = " << maximumSumSubarray(arr, n) <<endl;
return 0;
}輸出
當您編譯並執行上述程式時，它將生成以下輸出 -
Result = 9
更新於: 2020 年 1 月 30 日
635 次瀏覽
廣告