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