天威难测

用户名：uq_61498387617

访问量：1092

签　名：

岁月在你我呼吸间流浪

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

　　自我简介：

TA的其他文章

利用最大公因数来求解
浏览：100

就很简单的原理
浏览：136

你可能喜欢

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

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

[python]动态规划&遍历

　　作者: 天威难测　　　　发表时间：2022-02-20 17:44:24 浏览：132　|　评论：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语言程序设计教程（第三版）课后习题10.4 （C语言代码）

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

C二级辅导-计负均正（C语言代码）

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

[python]动态规划&遍历

评论区

精彩推荐

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

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

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

三角形（C++代码）递推

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

1025题解

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

1050题解（结构体数组与结构体指针的使用）

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

程序员的表白（C语言代码）

天威难测

TA的其他文章

你可能喜欢

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

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

C二级辅导-计负均正 （C语言代码）

字符逆序 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

[python]动态规划&遍历

评论区

精彩推荐

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

剪刀石头布 （C语言代码）不知道怎么直接在scanf中用枚举变量

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

三角形 （C++代码）递推

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

1025题解

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

1050题解（结构体数组与结构体指针的使用）

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

程序员的表白 （C语言代码）

C二级辅导-计负均正（C语言代码）

字符逆序（C语言代码）

　　评论区

剪刀石头布（C语言代码）不知道怎么直接在scanf中用枚举变量

三角形（C++代码）递推

程序员的表白（C语言代码）