算法--动态规划--最大子数组求和 C/C++

首先呢，我们要先了解什么是动态规划，注意动态俩字，那就说明他是动态的对吧。

我们定义一个变量temp，然后我们可以随时随地的给temp赋值，

比如：temp=max(temp+arr[i]，arr[i]);我们可以发现在每次的for循环中temp的值都可能发生改变。

代码实现：

#include<iostream>
using namespace std;

void MaxSubArray(int arr[], int length) {
	int num = length;
	if (length == 0) {//判断数据量是否合法
		exit(0);
	}
	int temp[100];//随便定义的大小，尽量大于等于数据量
	temp[0] = arr[0];
	int res = arr[0];
	for (int i = 1; i < length; i++) {
		temp[i] = max(temp[i - 1] + arr[i], arr[i]);//尝试比较arr[0]+arr[1]和arr[1]的大小，取最大的哪一个
		res = max(res, temp[i]);//取最大的一个
	}
	cout << res ;
}
int main() {
	//int arr[12] = { 1,-2,4,5,-2,8,3,-2,6,3,7,-1 };
	int arr[100];
	int n;
	cout << "输入数据的个数(n<=100)：";
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	MaxSubArray(arr, n);
	return 0;
}