C++动态规划------最大子段和的问题

深藏阁楼爱情的钟 2024-03-22 12:11 77阅读 0赞

**目录**

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

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

4.4 最大子段和

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

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

代码；

改进：

运行结果：

--------------------

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

![48c5cdb007f24b53bce876e79a85f73a.png][]

![2dd8cb4428e34a7fa6c80e704c4231f6.png][]

![0f5e894ee45e4df29202aa91a5e58ecc.png][]

#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][http_t.csdn.cn_6zZOk]

--------------------

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

### **4.4** **最大子段和** ###

![03876fd5d3014969a930b4d877ba0171.png][]

![bbdd6e8162d24421b79f980f56b4370d.png][]

![8c503eed42214872ab4d759e35ba5ddc.png][]

### **算法****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****计算最大子段和的动态规划算法的最优解** ###

![c561f944ccd748faa5a03a32fa3c1ce1.png][]

<table style="width:454pt;"> 
 <tbody> 
 <tr> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:104pt;"> i </td> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 1 </td> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 2 </td> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 3 </td> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 4 </td> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 5 </td> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 6 </td> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 7 </td> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 8 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:104pt;"> a[i] </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 1 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> -3 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 7 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 8 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> -4 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 12 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> -10 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 6 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:104pt;"> b </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 1 </td> 
 <td style="background-color:#ffede8;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> -2 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 7 </td> 
 <td style="background-color:#ffede8;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 15 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 11 </td> 
 <td style="background-color:#ffede8;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 23 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 13 </td> 
 <td style="background-color:#ffede8;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 19 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:104pt;"> sum </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 1 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 1 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 7 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 15 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 15 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 23 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 23 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 23 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:104pt;"> besti/begin </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 1 </td> 
 <td style="background-color:#ffede8;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 1 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 3 </td> 
 <td style="background-color:#ffede8;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 3 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 3 </td> 
 <td style="background-color:#ffede8;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 3 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 3 </td> 
 <td style="background-color:#ffede8;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 3 </td> 
 </tr> 
 <tr> 
 <td style="background-color:#fe8637;border-color:#ffffff;text-align:center;vertical-align:middle;width:104pt;"> bestj </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 1 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 1 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 3 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 4 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 4 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 6 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 6 </td> 
 <td style="background-color:#ffd9ce;border-color:#ffffff;text-align:center;vertical-align:middle;width:44pt;"> 6 </td> 
 </tr> 
 </tbody> 
</table>

#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;
 }

### 运行结果： ###

![b7454a1a15ef47918957176d600debd3.png][]

[48c5cdb007f24b53bce876e79a85f73a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/7e2b2b453a2b4f24859ad4be8c73f830.png
[2dd8cb4428e34a7fa6c80e704c4231f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/14e42bd49e2d4e3fb1b93383e0c4bfbb.png
[0f5e894ee45e4df29202aa91a5e58ecc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/f14562d017d748cc80eb6faa67d81764.png
[http_t.csdn.cn_6zZOk]: http://t.csdn.cn/6zZOk
[03876fd5d3014969a930b4d877ba0171.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/96554f00a44d47a89a7c686c84ab892f.png
[bbdd6e8162d24421b79f980f56b4370d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/c6633911af3d443f97264d2f3ca046fc.png
[8c503eed42214872ab4d759e35ba5ddc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/94000151c46547688205da1da661905e.png
[c561f944ccd748faa5a03a32fa3c1ce1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a1753627a8b64aebb0871ada273caa19.png
[b7454a1a15ef47918957176d600debd3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/9cfade0dad9d4c4ab4b6f9d11391559b.png