主要思想：

  • 由局部最优推导全局最优，并且举不出明显的反例
  • 需要自己思考，没有必要进行数学证明。

1、饼干分发

优先用大饼喂大胃

  1.     // 思路2：优先考虑胃口，先喂饱大胃口
  2.     public int findContentChildren(int[] g, int[] s) {
  3.         Arrays.sort(g);
  4.         Arrays.sort(s);
  5.         int count = 0;
  6.         int start = s.length - 1;
  7.         // 遍历胃口
  8.         for (int index = g.length - 1; index >= 0; index--) {
  9.             //保证别报错
  10.             // g[index] <= s[start] 大饼干优先满足大胃口。
  11.             if(start >= 0 && g[index] <= s[start]) {
  12.                 start--;
  13.                 count++;
  14.             }
  15.         }
  16.         return count;
  17.     }

小饼干优先满足小胃口

2、最长子序列

本题中的局部思想，是通过简单求和，如果和大于result，则对result进行赋值，否则将局部和赋值为0，类似与左右值的变化

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         if (nums.length == 1){
  4.             return nums[0];
  5.         }
  6.         int result =  Integer.MIN_VALUE;//记录min值，用于做比较
  7.         int count = 0;
  8.         for (int i = 0; i < nums.length; i++) {
  9.             count = count + nums[i]; //局部和
  10.             if (count > result) {
  11.                 result = count; //将最终结果和局部和进行比较
  12.             }
  13.             if (count <= 0) {
  14.                 count = 0;  //索引下标不变，变得是总和，其实也想到与改变下标
  15.             }
  16.         }
  17.         return result;
  18.     }
  19. }

3、股票最大值

主要思想参考上题，赋值两个变量，分别记录局部最优和全局最优，在局部最优逻辑中，用两天的值进行比较

  1.     public int maxProfit(int[] prices) {
  2.         if (prices.length == 0) {
  3.             return 0;
  4.         }
  5.         int sum = 0; //综合
  6.         int count = 0;  //局部和
  7.         for (int i = 1; i < prices.length; i++) {
  8.             if (prices[i - 1] > prices[i]) {
  9.                 count = 0;
  10.             } else {
  11.                 count += (prices[i] - prices[i - 1]);
  12.             }
  13.             sum += count;
  14.         }
  15.         return sum;
  16.     }

优化版

  1.    public int maxProfit(int[] prices) {
  2.         int result = 0;
  3.         for (int i = 1; i < prices.length; i++) {
  4.             result += Math.max(prices[i] - prices[i - 1], 0);
  5.         }
  6.         return result;
  7.     }

4、跳跃游戏

从第一步开始跳，当前位置能到的最远距离：nums[i] + i ，再用converge = Math.max(converge, nums[i] + i) 与目标位置进行判断，如果能到达则返回true

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         if (nums.length==1) return true;
  4.         int converge = 0;
  5.         for (int i = 0; i <= converge; i++) { //设定范围，第一步可以直接走
  6.             converge = Math.max(converge, nums[i] + i);  //后续取步数最大值
  7.             if (converge >= nums.length - 1) {
  8.                 return true;
  9.             }
  10.         }
  11.         return false;
  12.     }
  13. }

5、K 次取反后最大化的数组和

思路： 对于数组中的值有三种情况

  • 全是正数：选择较小的数字或者多次反转
  • 全是负数：选择