六六力扣刷题贪心算法之基础和最大子序和

六六力扣刷题贪心算法之基础和最大子序和

前言

之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两台晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀

今天是我做贪心算法的第一天，然后我跟大家一起来先来对贪心的一些概念和一些基础知识来学习下先

贪心算法概念

贪心算法（greedy algorithm [8] ，又称贪婪算法）是指，在对​​问题求解​​​时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，​​算法​​得到的是在某种意义上的局部最优解 [1] 。

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

贪心算法特性

有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币 。随着算法的进行，将积累起其他两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象 。有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优 。还有一个函数检查是否一个候选对象的集合是可行的，即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性 。选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解 。最后，目标函数给出解的值 。

什么情况下，我们应该使用贪心算法

利用贪心法求解的问题应具备如下2个特征

一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解 。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析

贪心的套路，模版

贪心算法一般分为如下四步：

将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解

其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。

最大子序和题目

给你一个整数数组 ​​nums​​ ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

输入： nums = [-2,1,-3,4,-1,2,1,-5,4]输出： 6解释： 连续子数组 [4,-1,2,1] 的和最大，为 6 。

题解

package com.six.finger.leetcode.five;/*```输入： nums = [-2,1,-3,4,-1,2,1,-5,4]输出： 6解释： 连续子数组 [4,-1,2,1] 的和最大，为 6 。``` */public class twentytwo { public static void main(String[] args) { } public static int getMax(int[] nums) { //首先定义我们的返回值 int res = Integer.MIN_VALUE; //定义局部最优解 int temp = 0; //遍历nums for (int num : nums) { //算一算局部的解 temp = temp + num; //把局部解和全局解比较，得出最优 res = Math.max(res, temp); // 判断局部的解，如果小于0，就给他变成0 if (temp < 0) { temp = 0; } } return res; }}

结束

好了，今天的分享就到这里了，其实我们今天就讲了下贪心算法的概念，和一道最简单的题，后面我们慢慢继续刷，好了，今天就到这，我是小六六三天打鱼，两天晒网！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。