连续子数组最大和

• 题目
• 解题思路
• 代码
• 引申

这是一道经典的动态规划入门题，首先还是需要找到转移方程，n为数组长度，先初始化一个长度为n的dp数组，对于一个给定的数组num[n]，我们依次遍历num数组，将遍历的每一个数 num[i] 与 dp[i-1]+num[i] 比较大小,取较大者为dp[i],用转移方程表达就是 dp[i]= max(dp[i-1]+num[i],num[i]) 目的在于完成一个dp数组，从而可以找寻最大和。

下面展示 完整代码

#include
using namespace std;
 int main(){
	 ios::sync_with_stdio(false);
	 int n;
	 cin>>n;
	 long long int num[n+1];
	 long long int dp[n+1];
	 memset(dp,0,sizeof(dp));
	 memset(num,0,sizeof(num));
	 for(int i=1;i<=n;i++){
		 cin>>num[i];
	 }
	 dp[1]=num[1];
	 for(int i=2;i<=n;i++){
		 dp[i]=max(dp[i-1]+num[i],num[i]);
	 }
	 int r=1;
	 for(int i=1;i<=n;i++){
		 if(dp[r] 
引申 
#贪心算法实现：后续补充

#假设需要输出该连续子数组：在前面动态规划的基础上得到dp数组，不难发现，
最大和子数组的位置对应在dp数组中的第一位有dp[i]=num[i],故可以先在dp数组中
找到最大值dp[i],最大值dp[i]的下标i在dp数组中向前移动, 直到找到dp[i]=
num[i]为止。
例如下面：
num  1 2 -1 -2 *2 1 -2 1 4* -5 4
dp   1 3  2  0 *2 3  1 2 6*  1 5
最大和的连续子数组为[2,1,-2,1,4],连续子数组最大和为6
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5658093.html