資料結構
網路
關係型資料庫管理系統
作業系統
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
更新於： 16-6 月-2020
712瀏覽
廣告