目录

最大子段和（动态规划C++）

 最大子段和的动态规划算法

4.4 最大子段和

算法4.7计算最大子段和的动态规划算法

 算法4.8计算最大子段和的动态规划算法的最优解

代码；

改进：

运行结果：

---

最大子段和（动态规划C++）

#include <iostream>
using namespace std;

//求最大子段和算法 
int MaxSum(int *a,int n) {
	int sum = 0, b = 0;
	for (int i = 1; i <= n; i++) {
		if (b > 0) {
			b += a[i];
		} else {
			b = a[i];
		}
		if (b > sum) {
			sum = b;
		}
	}
	return sum;
}

int main() {
	int a[100], n;
	cout << "请输入元素个数：";
	cin >> n;
	cout << "请输入各个元素：";
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cout << endl << "序列(";
	for (int i = 1; i <= n; i++) {
		if (i == n) {
			cout << a[i] << ")";
		} else {
			cout << a[i] << ",";
		}
	}
	cout << "的最大子段和为：" << MaxSum(a, n) << endl;
	return 0; 
}

参考：http://t.csdn.cn/6zZOk 

---

 最大子段和的动态规划算法

4.4 最大子段和

	1	2	3	4	5	6
a[i]	-2	11	-4	13	-5	-2
b(初值=0)	-2	11	7	20	15	13
sum	0	11	11	20	20	20

算法4.7计算最大子段和的动态规划算法

#define NUM 1001
int a[NUM];
int MaxSum(int n)
{
	int sum=0; 
	int b=0;
	for (int i=1;i<=n;i++)
	{
		if (b>0) b+=a[i]; else b=a[i];
		if (b>sum) sum=b;
	}
	return sum;
}

显然该算法的计算时间为O(n) 

 算法4.8计算最大子段和的动态规划算法的最优解

i	1	2	3	4	5	6	7	8
a[i]	1	-3	7	8	-4	12	-10	6
b	1	-2	7	15	11	23	13	19
sum	1	1	7	15	15	23	23	23
besti/begin	1	1	3	3	3	3	3	3
bestj	1	1	3	4	4	6	6	6

#define NUM 1001
int a[NUM];
int MaxSum(int n, int &besti, int &bestj)
{
　　int sum=0; 
　　int b=0;
　　int begin = 0;
　　for (int i=1;　i<=n;　i++)
　　{
	if (b>0)　 b+=a[i]; 
	else {b=a[i];　begin = i;}
 	if (b>sum) //得到新的最优值时，更新最优解
	{
	　　sum = b; 
	　　besti = begin; 
	　　bestj = i;
	}
　　}
　　return sum;
}

---

代码；

#include<iostream>
using namespace std;

const int NUM = 1001;
int a[NUM];

int MaxSum(int n,int &best_i,int &best_j) {
	int sum = 0;
	int b = 0;

	//当b[i-1]<0时，记录b[i]=a[i]的位置
	int begin = 0;
	for (int i = 1; i <= n; i++) {
		if (b > 0)
			b += a[i];
		else {
			b = a[i];
			begin = i;
		}
		if (b > sum) {
			sum = b;
			//得到新的最优值时，更新最优解
			best_i = begin;
			best_j = i;
		}
	}
	return sum;
}
int main() {
	int n;
	int i=0;
	int j = 0;
	int a[] = { 1,-3,7,8,-4,12,-10,6 };
	cin >> n;
	cout << endl;
	cout<<MaxSum(n,i,j);
	return 0;
}

改进：

#include<iostream>
using namespace std;

const int NUM = 1001;
int MaxSum(int a[], int n, int& best_i, int& best_j) {
    int sum = 0;
    int b = 0;

    //当b[i-1]<0时，记录b[i]=a[i]的位置
    int begin = 0;
    for (int i = 1; i <= n; i++) {
        if (b > 0)
            b += a[i];
        else {
            b = a[i];
            begin = i;
        }
        if (b > sum) {
            sum = b;
            //得到新的最优值时，更新最优解
            best_i = begin;
            best_j = i;
        }
    }
    return sum;
}

int main() {
    int n;
    int i = 0;
    int j = 0;
    cout << "请输入数组大小：";
    cin >> n;
    int arr[NUM];
    cout << "请输入数组元素：";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "最大连续子段和为：" << MaxSum(arr, n, i, j) << endl;
    cout << "最大连续子段为：";
    for (int k = i - 1; k < j; k++) {
        cout << arr[k] << " ";
    }
    return 0;
}

运行结果：