53. 最大子序和 golang (动态规划与贪心算法)
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。
如果现在的和成了负数,那么就从下一个大于0的数字开始
在整个数组或在固定大小的滑动窗口中找到总和或最大值或最小值的问题可以通过动态规划(DP)在线性时间内解决。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解
找到当前区间的最优解,而贪心算法是
动态规划和贪心算法
到此这篇关于“53. 最大子序和 golang (动态规划与贪心算法)”的文章就介绍到这了,更多文章或继续浏览下面的相关文章,希望大家以后多多支持JQ教程网!您可能感兴趣的文章:
53. 最大子序和 golang (动态规划与贪心算法)
go基础算法思想
golang sdk后端怎么用_Golang资深后端工程师需要了解的知识点
PHP变量命名规则详解
《编程之美》读书笔记(四): 卖书折扣问题的贪心解法
《贪吃蛇》--H5小游戏开发
01背包问题动态规划
数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
Python如何求解最长公共子序列
golang微服务框架对比_斗鱼开源首秀——基于 Go 的微服务框架 Jupiter