教程集 > Golang编程 > golang教程 > 正文 53. 最大子序和 golang （动态规划与贪心算法）

53. 最大子序和 golang （动态规划与贪心算法）

发布时间：2022-01-19 编辑：jiaochengji.com

教程集为您提供53. 最大子序和 golang （动态规划与贪心算法）等资源，欢迎您收藏本站，我们将为您提供最新的53. 最大子序和 golang （动态规划与贪心算法）资源

<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"/></svg><h1>题目</h1>

给定一个整数数组 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

<h1>贪心算法</h1> <blockquote>

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。
如果现在的和成了负数，那么就从下一个大于0的数字开始

</blockquote> <pre><code class="lang-go hljs"><span class="token keyword">func</span> <span class="token function">maxSubArray</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">{</span> <span class="token keyword">return</span> nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token punctuation">}</span> <span class="token keyword">var</span> currSum<span class="token punctuation">,</span> maxSum <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token keyword">for</span> <span class="token boolean">_</span><span class="token punctuation">,</span> v <span class="token operator">:=</span> <span class="token keyword">range</span> nums <span class="token punctuation">{</span> <span class="token keyword">if</span> currSum <span class="token operator">></span> <span class="token number">0</span> <span class="token punctuation">{</span> currSum <span class="token operator"> =</span> v <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> currSum <span class="token operator">=</span> v <span class="token punctuation">}</span> <span class="token keyword">if</span> maxSum <span class="token operator"><</span> currSum <span class="token punctuation">{</span> maxSum <span class="token operator">=</span> currSum <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> maxSum <span class="token punctuation">}</span> </code></pre> <h1>动态规划</h1> <blockquote>

在整个数组或在固定大小的滑动窗口中找到总和或最大值或最小值的问题可以通过动态规划（DP）在线性时间内解决。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解
找到当前区间的最优解，而贪心算法是

</blockquote> <pre><code class="lang-go hljs"><span class="token keyword">func</span> <span class="token function">maxSubArray</span><span class="token punctuation">(</span>nums <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span> max_sum <span class="token operator">:=</span> nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token function">len</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator"> </span> <span class="token punctuation">{</span> <span class="token keyword">if</span> nums<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">></span> <span class="token number">0</span> <span class="token punctuation">{</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator"> =</span> nums<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">></span> max_sum <span class="token punctuation">{</span> max_sum <span class="token operator">=</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> max_sum <span class="token punctuation">}</span> </code></pre> <h1>参考</h1>

动态规划和贪心算法

<blockquote class="layui-elem-quote" style="width: 100%;overflow:hidden"> 作者： csdn_kou
链接： https://blog.csdn.net/csdn_kou/article/details/104259887
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
</blockquote>

到此这篇关于“53. 最大子序和 golang （动态规划与贪心算法）”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
53. 最大子序和 golang （动态规划与贪心算法）
go基础算法思想
 golang sdk后端怎么用_Golang资深后端工程师需要了解的知识点
 PHP变量命名规则详解
 《编程之美》读书笔记(四): 卖书折扣问题的贪心解法
 《贪吃蛇》--H5小游戏开发
 01背包问题动态规划
 数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
 Python如何求解最长公共子序列
 golang微服务框架对比_斗鱼开源首秀——基于 Go 的微服务框架 Jupiter

上一篇：Golang 浮点数格式化输出，保留一位小数下一篇：Go语言并发模型：以并行处理MD5为例

[关闭]

最近更新

浏览排行

~ ~