算法-贪心思想

　　　　庭前看玉树，肠断忆连枝

一、剪绳子

1、题目描述

把一根绳子剪成多段，并且使得每段的长度乘积最大。

n = 2
return 1 (2 = 1 + 1)

n = 10
return 36 (10 = 3 + 3 + 4)

2、解题思路

贪心

尽可能得多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现。如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。以下为证明过程。

将绳子拆成 1 和 n-1，则 1(n-1)-n=-1<0，即拆开后的乘积一定更小，所以不能出现长度为 1 的绳子。

将绳子拆成 2 和 n-2，则 2(n-2)-n = n-4，在 n>=4 时这样拆开能得到的乘积会比不拆更大。

将绳子拆成 3 和 n-3，则 3(n-3)-n = 2n-9，在 n>=5 时效果更好。

将绳子拆成 4 和 n-4，因为 4=2*2，因此效果和拆成 2 一样。

将绳子拆成 5 和 n-5，因为 5=2+3，而 5<2*3，所以不能出现 5 的绳子，而是尽可能拆成 2 和 3。

将绳子拆成 6 和 n-6，因为 6=3+3，而 6<3*3，所以不能出现 6 的绳子，而是拆成 3 和 3。这里 6 同样可以拆成 6=2+2+2，但是 3(n - 3) - 2(n - 2) = n - 5 >= 0，在 n>=5 的情况下将绳子拆成 3 比拆成 2 效果更好。

继续拆成更大的绳子可以发现都比拆成 2 和 3 的效果更差，因此我们只考虑将绳子拆成 2 和 3，并且优先拆成 3，当拆到绳子长度 n 等于 4 时，也就是出现 3+1，此时只能拆成 2+2。

 1 public class Solution {
 2     public int cutRope(int target) {
 3         if(target < 2){
 4             return 0;
 5         }
 6         if(target == 2){
 7             return 1;
 8         }
 9         if(target == 3){
10             return 2;
11         }
12         /*
13          * 8/3 = 2, 9/3 =3, 10/3 =3
14          */
15         int timeOf3 = target /3; // 3的倍数
16         if(target - timeOf3 * 3 == 1){
17             timeOf3--;
18         }
19         int timeOf2 = (target - timeOf3 * 3) / 2;  // 2的倍数
20         return (int)(Math.pow(3, timeOf3)) * (int)(Math.pow(2, timeOf2));
21         
22     }
23 }

二、股票的最大利润

1、题目描述

可以有一次买入和一次卖出，买入必须在前。求最大收益。

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

2、解题思路

使用贪心策略，假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。因此在遍历数组时记录当前最低的买入价格，并且尝试将每个位置都作为卖出价格，取收益最大的即可。

 1 class Solution {
 2     public int maxProfit(int[] prices) {
 3         if(prices == null || prices.length == 0){
 4             return 0;
 5         }
 6         int soFarMin = prices[0];
 7         int maxProfit = 0;
 8         for(int i = 1; i < prices.length; i++){
 9             soFarMin = Math.min(soFarMin, prices[i]);
10             // 返回参数中的最大值 Math.max()
11             maxProfit = Math.max(maxProfit, prices[i] - soFarMin);
12         }
13         return maxProfit;
14     }
15 }

庭前看玉树

肠断忆连枝