python题目及答案大一大学生蓝桥杯python题目python题目查询
下载地址 https://share.weiyun.com/OvviwGnZ
资料目录
Python练习集100题
100道Python面试题
Python100经典练习题
Python经典题目100道题
Python题库(已收录100道真题）
Python100例视频讲解课程
菜鸟教程Python教程100例
130道python练习题，涵盖基础内容的方方面面
Python考试题复习知识点试卷试题
PYTHON测试题和答案
python第一阶段考试题
Python经典面试题和答案解析
python期末考试复习试卷
python习题集大全（附答案解析）
老男孩Python全栈7期练习题（面试真题模拟）
尚观python第一阶段考试（面试真题模拟）
《Python程序设计基础与应用》习题答案
《Python快速编程入门》——课后题答案
Python编程基础张健 , 张良均课后习题及答案
Python程序设计基础及实践（慕课版）郭炜习题答案
Python程序设计基础习题答案与分析
python基础试题(含答案)
举例 最大子序和
一个列表里，都是整数，请到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
例如列表 [-2,1,-3,4,-1,2,1,-5,4]， 其连续子数组[4,-1,2,1]的和最大为6.
思路分析
动态规划的算法，难与易只在一念之间，掌握了动态规划的精髓，代码轻易的就能写出，反之，则陷入到茫然之中。
动态规划的题目，其实，都可以用暴力破解，但真正的解法都非常的巧妙，说是巧妙，并不是投机取巧，而是掌握了动态规划的实质。
既然是动态，那么到底是什么在动呢？假设数组为k，令max_sum表示最大子数组之和，已知从k[i]到[j]的的和为pre_sum，暂且让max_sum = pre_sum，那么现在，我们要考虑是否应该让k[j+1]也加到这个子数组之中，多一个数，可能让max_sum更大哦。
如果pre_sum >=0 ,那么就让pre_sum += k[j+1]，你一定会提出质疑，如果k[j+1]是负数，那么子数组之和不是更小了么？这里你忽略了，我已经让max_sum=pre_sum，所以我已经记录了最大值，pre_sum+= k[j+1]之后，的确变小了，但是max_sum还是之前的那个最大值，之所以要加k[j+1]，因为k[j+2]有可能是一个很大的正数啊，所以要继续探索可能的最大子数组之和。那么假如k[j+2]也是负数呢，而且是很大的负数，以至于加上k[j+2]之后，pre_sum<0, 如果这样的事情发生，就按下面的方法操作
如果pre_sum < 0,不论k[j+1]是正还是负，k[j+1]加上pre_sum以后所得到的和都一定比k[j+1]更小，而我们要的是最大子序之和，所以这时，应该让max_sum等于pre_sum和k[j+1]中最大的那个，同时，让pre_sum = k[j+1]，表示重新开始寻找和最大的子数组，如果不重新开始，带着pre_sum这个负数，难道对求和不是一个负面效果么。
谁在动呢，是pre_sum一直在动，我们规划的是一个子数组，期初，这个子数组里只有一个元素，就是数组的第一个元素k[0],随后就是考虑要不要把k[1]加进来，是否加进来，就按照上面的说的方法来进行。
示例代码
# coding=utf-8
def max_sub_sum(lst):
max_sum = lst[0]
pre_sum = lst[0] # pre_sum是动态的,最初等于列表的第一个元素
for i in range(1, len(lst)):
# 前面的累积和如果小于0,当前值item加上一个负数只会比item更小
# 因此将item赋值给pre_sum
if pre_sum < 0:
pre_sum = lst[i]
else:
# 前面的累积和是整数或者0,继续累加
pre_sum += lst[i]
if pre_sum > max_sum:
max_sum = pre_sum
return max_sum
if __name__ == "__main__":
print max_sub_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
小结
既然是动态规划，就要找到那个变化的点，就这道题目而言，变化的点就是连续子数组之和小于0了，这个时候就必须从新开始寻找了，因为这个和已经是负数了，就如同一个包袱，就算后面的数都是正数，加上一个负数也终究比都是整数要小。
|