1 题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组[4,-1,2,1] 的和最大，为 6。
2 思路描述
第一时间想到的当然是暴力解决，基本思路就是遍历一遍，用两个变量，一个记录最大的和，一个记录当前的和。后面发现可以用贪心算法来解比较简单其基本思路是正在访问的节点值+此节点之前的最大值如果大于当前节点，则更新最大值为和，否则更新最大值为当前节点。
3 暴力解决的代码
nums=[-2,1,-3,4,-1,2,1,-5,4]
|
4 贪心算法的代码
nums=[-2,1,-3,4,-1,2,1,-5,4] lenth = len(nums) cur_sum=max_sum = nums[0] for i in range(1,lenth): cur_sum = max(cur_sum+nums[i], nums[i]) max_sum = max(cur_sum, max_sum) print(max_sum) |
5 总结
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。
