数据结构
网络
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 浏览量
广告