最大总和连续子数组
给出了一个整数数组。我们必须找到所有元素的总和，这些元素的总和最大，这些元素将作为输出发送。
使用动态编程，我们将存储当前项的最大和。这将有助于找到数组中连续元素的总和。
输入输出
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