資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝學
法學使用分治演算法在 C++ 中計算最大子陣列和
假設我們有一個包含正值和負值的資料列表。我們需要找到和最大的連續子陣列的和。假設列表包含 {-2, -5, 6, -2, -3, 1, 5, -6}，則最大子陣列的和為 7，即子陣列 {6, -2, -3, 1, 5} 的和。
我們將使用分治法來解決這個問題。步驟如下 -
步驟 -
- 將陣列分成兩部分
- 找出以下三者中的最大值
- 左子陣列的最大子陣列和
- 右子陣列的最大子陣列和
- 使子陣列跨過中點的最大子陣列和
示例
#include <iostream>
using namespace std;
int max(int a, int b) {
return (a > b)? a : b;
}
int max(int a, int b, int c) {
return max(max(a, b), c);
}
int getMaxCrossingSum(int arr[], int l, int m, int h) {
int sum = 0;
int left = INT_MIN;
for (int i = m; i >= l; i--) {
sum = sum + arr[i];
if (sum > left)
left = sum;
}
sum = 0;
int right = INT_MIN;
for (int i = m+1; i <= h; i++) {
sum = sum + arr[i];
if (sum > right)
right = sum;
}
return left + right;
}
int maxSubArraySum(int arr[], int low, int high) {
if (low == high)
return arr[low];
int mid = (low + high)/2;
return max(maxSubArraySum(arr, low, mid), maxSubArraySum(arr, mid+1, high), getMaxCrossingSum(arr, low, mid, high));
}
int main() {
int arr[] = {-2, -5, 6, -2, -3, 1, 5, -6};
int n = sizeof(arr)/sizeof(arr[0]);
int max_sum = maxSubArraySum(arr, 0, n-1);
printf("Maximum contiguous sum is %d", max_sum);
}輸出
Valid String
更新日期： 2019 年 10 月 21 日
440 次瀏覽
廣告