資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學最大連續子陣列和
給定一個整數陣列。我們必須找到所有相鄰元素之和，其和最大，然後輸出該和。
使用動態規劃，我們將儲存到當前項的最大和。這有助於找出陣列中相鄰元素的和。
輸入和輸出
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
更新：2020 年 6 月 16 日
711 次瀏覽
廣告