算法>贪心算法理论基础

算法>贪心算法是一种在每一步选择中都做出当前看起来最优的选择，从而期望通过局部最优解得到全局最优解的算法。算法>贪心算法的基本思想是：在解决问题时，尽量选择当前最好的选项，最终达到全局最优解.

分发饼干

题目：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。

for循环不利于控制移动，舍弃这种普遍思维，习惯用变量的移动控制，学习数据处理的元素控制，区分识别动态，非动态，目标值，固定值。

public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0,index = s.length-1;for(int i = g.length-1;i>=0;i--){if(index>=0&&s[index]>=g[i]){index--;count++;}}return count;        }

---

摆动序列

以下是一些定义：
特别地，对于长度为 1 的序列，它既是「上升摆动序列」，也是「下降摆动序列」。

序列中的某个元素被称为「峰」，当且仅当该元素两侧的相邻元素均小于它。如序列 [1,3,2,4] 中，3 就是一个「峰」。

序列中的某个元素被称为「谷」，当且仅当该元素两侧的相邻元素均大于它。如序列 [1,3,2,4] 中，2 就是一个「谷」。

特别地，对于位于序列两端的元素，只有一侧的相邻元素小于或大于它，我们也称其为「峰」或「谷」。如序列 [1,3,2,4] 中，1 也是一个「谷」，4 也是一个「峰」。

因为一段相邻的相同元素中我们最多只能选择其中的一个，所以我们可以忽略相邻的相同元素。现在我们假定序列中任意两个相邻元素都不相同，即要么左侧大于右侧，要么右侧大于左侧。对于序列中既非「峰」也非「谷」的元素，我们称其为「过渡元素」。如序列 [1,2,3,4] 中，2 和 3 都是「过渡元素」。

解题：模拟图像，将数字差值变成坡度。

1. 上下坡中有平坡

舍弃curdiff = 0，平坡时差值为0。

2.数组首尾两端

题目中限定了：仅有一个元素或者含两个不等元素的序列也视作摆动序列。

3.单调坡度有平坡

当某段大体成递增趋势时，只用考虑最高波峰，与初始过渡元素。

  public int wiggleMaxLength(int[] nums) {int prediff = 0,curdiff = 0;//prediff相当于初始0，curdiff是当前值int result = 1;//最右端的for (int i = 0; i < nums.length-1; i++) {curdiff = nums[i+1] - nums[i];if((prediff >= 0&&curdiff<0)||(prediff <= 0&&curdiff>0)){result++;prediff = curdiff;//记录递增的第一个，后面若没遇到摆动的话，不必进行记录}}//某段是递增序列，递减序列。//连续递增序列return result;}

---

最大子序和

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
方法：贪心。

贪心贪的是哪里呢？

如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

误区：如果输入用例都是-1，或者 都是负数，这个算法>贪心算法跑出来的结果是 0， 这是又一次证明脑洞模拟不靠谱的经典案例，实际为最大负数。

 public int maxSubArray(int[] nums) {int result = Integer.MIN_VALUE;int count = 0;for (int i = 0; i < nums.length; i++) {count += nums[i];if (count>result){result = count;}if (count<0){count =0;}}return result;}