資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究C/C++ 鄰接子陣列最大和程式？
給出整型陣列。我們需要找到和為連續的各元素。和最大的將輸出。
採用動態規劃，我們將儲存當前項的最大和。這將有助於在陣列中查詢連續元素的和。
Input: An array of integers. {-2, -3, 4, -1, -2, 1, 5, -3}
Output: Maximum Sum of the Subarray is : 7演算法
maxSum(array, n)
輸入 - 主陣列、陣列大小。
輸出 - 最大和。
Begin tempMax := array[0] currentMax = tempMax for i := 1 to n-1, do currentMax = maximum of (array[i] and currentMax+array[i]) tempMax = maximum of (currentMax and tempMax) done return tempMax End
示例
#include<iostream>
using namespace std;
int maxSum( int arr[], int n) {
int tempMax = arr[0];
int currentMax = tempMax;
for (int i = 1; i < n; i++ ) { //find the max value
currentMax = max(arr[i], currentMax+arr[i]);
tempMax = max(tempMax, currentMax);
}
return tempMax;
}
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = 8;
cout << "Maximum Sum of the Sub-array is: "<< maxSum( arr, n );
}輸出
Maximum Sum of the Sub-array is: 7
更新於: 30-Jul-2019
371 瀏覽量
廣告