天威难测

用户名：uq_61498387617

访问量：1162

签　名：

岁月在你我呼吸间流浪

等　　级
排　　名	8075
经　　验	1219
参赛次数	1
文章发表	10
年　　龄	0
在职情况	学生
学　　校	南京中医药大学
专　　业	中药学类

　　自我简介：

TA的其他文章

[python]动态规划&遍历
浏览：134

动态规划思考全过程
浏览：177

动态规划与优化后的动态规划哈哈哈哈
浏览：572

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （Java代码）

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

[python]动态规划&遍历

　　作者: 天威难测　　　　发表时间：2022-02-20 17:44:24 浏览：134　|　评论：0　

原题链接：蓝桥杯算法提高VIP-和最大子序列

# 问题描述
![在这里插入图片描述](https://img-blog.csdnimg.cn/e2212520b81a4e519572ca74fb4d371d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5aSp5aiB6Zq-5rWL,size_20,color_FFFFFF,t_70,g_se,x_16)

# 初始思路
最初想用**动态规划**，令 lis[] 为得到的数组，dp[i] 为到第 i 个数字时求和达到最大的值，所以可以得到递归式：

```python
dp[i] = max(dp[i - 1] + lis[i], dp[i])
```
并且要注意，由于代码从 0 开始的特殊性，所以首先如果总共有 n 个数，那就预定义 dp 列表中有 n + 1 个位置，并且把第一个预定义成0。

## 初始代码

```python
# main
n = int(input())
lis = [0 for _ in range(n + 1)]
dp = [0 for _ in range(n + 1)]
temp = input().split()
for i in range(n):
    lis[i + 1] = int(temp[i])

# dp
for i in range(1, n + 1):
    dp[i] = max(dp[i - 1] + lis[i], dp[i])

print(max(dp))
```

# 优化思路
上面的代码可以得到最后答案，但是超时了，于是研究后尝试用遍历的方法，就是依次加数，如果大于现有的最大值，那就将其定为现在的最大值。

## 优化代码

```python
# main
n = int(input())
lis = [0 for _ in range(n)]
temp = input().split()
for i in range(n):
    lis[i] = int(temp[i])

# dp
max_num = -10
now = 0
for item in lis:
    now = now + item
    if(now > max_num):
        max_num = now
    elif(now < 0):
        now = 0
print(max_num)
```
但是还是超时错误。。。我属实不太理解

# 最终解答！

我更改了列表的输入方式，然后就成功运行了，属实没想通原因。。。可能是input的长度限制吧。

```python
# main
n = int(input())
lis = [int(i) for i in input().split()]

# dp
max_num = -10
now = 0
for item in lis:
    now = now + item
    if(now > max_num):
        max_num = now
    elif(now < 0):
        now = 0
print(max_num)
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

天威难测

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （Java代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

[python]动态规划&遍历

评论区

精彩推荐

C二级辅导-统计字符（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

C语言训练-字符串正反连接（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

兰顿蚂蚁（C++代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言训练-大、小写问题（C语言代码）

【计算两点间的距离】（C语言代码）

DNA （C语言代码）

天威难测

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （Java代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

[python]动态规划&遍历

评论区

精彩推荐

C二级辅导-统计字符 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

C语言训练-字符串正反连接 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

兰顿蚂蚁 （C++代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

【计算两点间的距离】 （C语言代码）

DNA （C语言代码）

　　评论区

C二级辅导-统计字符（C语言代码）

C语言训练-字符串正反连接（C语言代码）

兰顿蚂蚁（C++代码）

C语言训练-大、小写问题（C语言代码）

【计算两点间的距离】（C语言代码）