【算法基础】动态规划：冲冲冲

博主： Fivk
发布时间：2021 年 09 月 01 日
1202 次浏览
暂无评论
1534字数
分类：算法基础

可以看看文章

<div class="inner-content" style="margin-left: 10px;">
<p class="inser-title">CSDN @ Hollis Chuang</p>
<div class="inster-summary text-muted">
告别动态规划，连刷40道动规算法题，我总结了动规的套路
</div>
</div>
</a>

</div>

</div>

不扯别的了，直接上题！！！

# 例题1：最大区间和

给定**K**个整数组成的序列{ **N****1******, **N****2******, ..., **N****K****** }，“连续子列”被定义为{ **N****i******, **N****i****+****1******, ..., **N****j****** }，其中 **1** **≤****i****≤****j****≤** **K**。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。

### 输入格式:

输入第1行给出正整数**K** (**≤** **100000**)；第2行给出**K**个整数，其间以空格分隔。

### 输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

### 输入样例:

```in
6
-2 11 -4 13 -5 -2
```

### 输出样例:

```out
20
```

可以使用前缀和完美解决，但动态规划思路更清晰。

直接想法：dp[i]表示前 i 个数中最大区间和，但是难以维护，效率低。

改进dp：dp[i] 表示以第 i 个数结尾的区间的区间和最大值，dp数组最大值为答案，全为负则为0。

状态转移方程dp[i] = max(a[i],a[i] + dp[i - 1])

计算dp[i]只需要dp[i - 1] 和 a[i]，所以 dp 数组和 a 数组可以滚动（可以不用数组记录）：dp = max(a,a+dp)

时间复杂度$O(N)$，空间复杂度$O(1)$。

- 滚动

```cpp
#include <iostream>
using namespace std;

int max(int a, int b)
{
	if(a > b) 
		return a;
	else
		return b;
}

int N,a,dp,ans;
int main()
{
	int i;
	cin >> N;
	for(i = 1; i <= N; i++)
	{
		cin >> a;
		dp = max(a,a + dp);
		ans = max(ans,dp); 
	}
	cout << ans <<endl;

return 0;
}
```

- 不滚动

```cpp
#include <iostream>
using namespace std;

int max(int a, int b)
{
	if(a > b) 
		return a;
	else
		return b;
}

int N,a[100],dp[100],ans;
int main()
{
	int i;
	cin >> N;
	for(i = 1; i <= N; i++)
	{
		cin >> a[i];
		dp[i] = max(a[i],a[i] + dp[i - 1]);
		ans = max(ans,dp[i]); 
	}
	cout << ans <<endl;

return 0;
}
```

最后修改：2021 年 09 月 12 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

本当迷
哈哈时过境迁再看一遍帆的文章质量还是那么高
挺胸的打工人
感谢博主分享
菜菜
一天就学一些我不知道的东西(´இ皿இ｀)
zhanqy
博主赛高！
null ？？［］
还可以把扩展运算符加上呀，这个很有用［…arr］，用于数组合...

【算法基础】动态规划：冲冲冲

Fivk • 2021 年 09 月 01 日

可以看看文章

不扯别的了，直接上题！！！

# 例题1：最大区间和

本题旨在测试各种不同的算法在各种数据情况下的表现。

### 输入格式:

输入第1行给出正整数**K** (**≤** **100000**)；第2行给出**K**个整数，其间以空格分隔。

### 输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

### 输入样例:

```in
6
-2 11 -4 13 -5 -2
```

### 输出样例:

```out
20
```

可以使用前缀和完美解决，但动态规划思路更清晰。

直接想法：dp[i]表示前 i 个数中最大区间和，但是难以维护，效率低。

改进dp：dp[i] 表示以第 i 个数结尾的区间的区间和最大值，dp数组最大值为答案，全为负则为0。

状态转移方程dp[i] = max(a[i],a[i] + dp[i - 1])

计算dp[i]只需要dp[i - 1] 和 a[i]，所以 dp 数组和 a 数组可以滚动（可以不用数组记录）：dp = max(a,a+dp)

时间复杂度$O(N)$，空间复杂度$O(1)$。

- 滚动

```cpp
#include <iostream>
using namespace std;

int max(int a, int b)
{
	if(a > b) 
		return a;
	else
		return b;
}

int N,a,dp,ans;
int main()
{
	int i;
	cin >> N;
	for(i = 1; i <= N; i++)
	{
		cin >> a;
		dp = max(a,a + dp);
		ans = max(ans,dp); 
	}
	cout << ans <<endl;

return 0;
}
```

- 不滚动

```cpp
#include <iostream>
using namespace std;

int max(int a, int b)
{
	if(a > b) 
		return a;
	else
		return b;
}

int N,a[100],dp[100],ans;
int main()
{
	int i;
	cin >> N;
	for(i = 1; i <= N; i++)
	{
		cin >> a[i];
		dp[i] = max(a[i],a[i] + dp[i - 1]);
		ans = max(ans,dp[i]); 
	}
	cout << ans <<endl;

return 0;
}
```

【算法基础】动态规划：冲冲冲

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

【Fivk】文章归档

回忆刚入天柱二中的我

【STL】for (auto x : nums)

【C】文件_文件打开关闭介绍

[函数快查] fputs -- 将一个字符串写入到文件中

【Redis】哨兵集群搭建一键启动和暂停

半夜三更的

【算法基础】动态规划：冲冲冲

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【算法基础】动态规划：冲冲冲

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款