动态规划刷题总结

逃离我推掉我的手 2022-09-24 15:28 170阅读 0赞

题目1：

##### 输出描述: #####

对于每组数据，输出一个整数，代表最长递增子序列的长度（不需要连续）。

##### 输入例子: #####

2
    7
    89 256 78 1 46 78 8
    5
    6 4 8 2 17

##### 输出例子: #####

3
    3

package dynamatic;
    
    import java.util.Scanner;
    
    public class D1 {
     
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNextInt()) {
            	//1.初始化
                int count = in.nextInt();      
                for (int i=0; i<count; i++) {
                    int length = in.nextInt();
                    int[] array = new int[length];
                    int[] values = new int[length];
                    for (int j=0; j<length; j++) {
                        array[j] = in.nextInt();
                    }
                    findMaxSLength(array, values);
                }
            }
         
        }
         //1.深度优先搜索
        public static void findMaxSLength(int[] array, int[] values) {       
            int length = array.length;
            for (int i=0; i<length; i++) {
                if (i==0) {
                    values[i] = 1;
                } else {
                     
                    int max = 0;
                    for (int j=i-1; j>=0; j--) {
                        if (array[j] < array[i]) {
                        	//2.关键的判断value[]--[1, 1, 2, 1, 3]在此基础上判断，倒推，动态更新
                            int temp = values[j] + 1;
                            if (temp > max) {
                                max = temp;
                            }
                        }
                        values[i] = max == 0?1:max;
                    }                
                }
            }        
            int max=0;
            for (int k : values) {
                if (k>max) {
                    max = k;
                }
            }
            System.out.print(max);    
        }
    }

**变化**

##### 输入例子: #####

2
    7
    89 256 78 1 46 78 8
    5
    6 4 8 2 17

##### 输出例子: #####

1 46 78
    6 8 17

package dynamatic;
    
    import java.util.Scanner;
    import java.util.List;
    import java.util.ArrayList;
     
    public class D22 {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
                int size = in.nextInt();
                for (int i = 0; i < size; i++) {
                    int len = in.nextInt();
                    int[] data = new int[len];
                    for (int j = 0; j < len; j++) {
                        data[j] = in.nextInt();
                    }
                    lisB(data);
                   
                }
               
            }
            in.close();
        }
     
        public static  void lisB(int[] array) { //dp时间复杂度（o(n2)）
        	//边界判断
            ArrayList<Integer> result = new ArrayList<>();
            if(array == null || array.length == 0) return;
            int length = array.length;
            //存储各个位置
            ArrayList<ArrayList<Integer>> buffer = new ArrayList<>();//每个索引下的最大子序列长度列
            //DFS
            for(int i = 0; i < length; i++) {
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(array[i]);
                buffer.add(temp);
                for(int j = i - 1; j >= 0; j--) {                
                    if(array[i] > array[j] && buffer.get(i).size() <= buffer.get(j).size()) {  //j < i && array[j] < array[i]
                        buffer.set(i,new ArrayList<Integer>(buffer.get(j)));   //
                        buffer.get(i).add(array[i]);
                    }
                    
                }
                if(result.size() < buffer.get(i).size()) {
                    result = buffer.get(i);
                }
            }
            
            for (int j = 0; j < result.size(); j++) {
            	if (j==result.size()-1) {
            		System.out.print(result.get(j));
    			}else {
    				
    				System.out.print(result.get(j)+" ");
    			}
    		}
           // return result;
        
        }
    }

**2.求CD个数**

你作为一名出道的歌手终于要出自己的第一份专辑了，你计划收录 n 首歌而且每首歌的长度都是 s 秒，每首歌必须完整地收录于一张 CD 当中。每张 CD 的容量长度都是 L 秒，而且你至少得保证同一张 CD 内相邻两首歌中间至少要隔 1 秒。为了辟邪，你决定任意一张 CD 内的歌数不能被 13 这个数字整除，那么请问你出这张专辑至少需要多少张 CD ？

##### 输入描述: #####

每组测试用例仅包含一组数据，每组数据第一行为三个正整数 n, s, L。 保证 n ≤ 100 , s ≤ L ≤ 10000

##### 输出描述: #####

输出一个整数代表你至少需要的 CD 数量。

##### 输入例子: #####

7 2 6

##### 输出例子: #####

package dynamatic;
    
    import java.util.*;
     
    public class D4CD{
         
        public static void main(String[] args){
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                int n = in.nextInt();//歌曲总数
                int s = in.nextInt();//每首哥的时间
                int l = in.nextInt();//CD容量
                int count = (l+1)/(s+1);//每张容纳多少歌曲---都加一个空，看为整体（最大值）
                count = Math.min(n, count);//防止歌曲过少
                if(count%13==0){
                    count--;
                }
                int sum = n/count;//需要多少CD
                int yu = n%count;//余数！！！！最后一个专辑剩下的歌曲
                /*
                 * yu是最后一张专辑的歌曲数，如果yu是13的倍数，为了不增加专辑的数量，---没张容纳》13
                 * 我们可以考虑从倒数第二张专辑中借一首歌，此时倒数第二张专辑的歌曲数是count-1，
                 * 若(count-1)==yu，这种情况只能在多出一张专辑。不知道有没有讲明白？我的表述有点不到位，防止最后count-1为13倍数。
                 * 
                 * */
                if(yu!=0){
                    sum++;
                    if(yu%13==0&&(count-yu)==1){//查看最后最后一张专辑的情况
                        sum++;
                    }
                }
                System.out.println(sum);
            }
        }
    }

**3.背包问题**

小萌是个WOW发烧友，每天都痴迷于他的法师号。精诚所至金石为开，小萌穿越到WOW的世界中了...  
初来乍到的小萌在暴风城的小巷中，遇见了一位善良的德鲁伊。德鲁伊听了小萌的故事，打算帮助他在WOW这个世界好好活下去，于是，把自己的东西都给了小萌了...  
德鲁伊的东西太多了，于是小萌去拍卖行买了几个包裹，一切妥当之后，小萌开始把东西装进包裹里。  
不过，因为小萌穿越时候脑袋先着地，所以脑子不好用，每次他拿起一个物品，要不装进包里，要不就直接扔掉...  
而且，一个背包一旦不往里装东西，小萌就会封上口不再用...  
现在，告诉你小萌每个物品的体积，背包的个数和容量，以及小萌拿物品的顺序，你要帮助小萌求出他能拿走多少东西。

##### 输入描述: #####

输入的第一行为一个整数T，代表测试数据组数。
    
      第一行：三个正整数 N、T、M。 分别表示物品的个数，背包的容量，背包个数。
    
      第二行：N个数。表示每个物品的体积。
    
      保证：
    
      1<=N,T,M<=20,0<=vi<=30

##### 输出描述: #####

对于每组数据，输出一个整数，代表小萌可以拿走的最多物品个数。

##### 输入例子: #####

2
    5 5 2
    4 3 4 2 1

##### 输出例子: #####

**例4：**

Alice 和 Bob 在玩一个取石子的游戏，有 n 堆石子，第 i 堆有 ai 个石子，两个人轮流行动，Alice 先手。每个人每次行动必须选择一堆非空的石子，拿走其中的一部分石子，谁不能行动谁就输了。

他们玩过很多次这个游戏之后都觉得太无聊了，于是决定给游戏增加一个要求：当某个人要拿第 i 堆中的石子时必须要保证第 1 .. i-1 堆的石子都已经拿光了。也就是说两个人必须先拿光第 1 堆中的石子，然后再拿第 2 堆的，第 3 堆的……以此类推。

所以现在问在这个新游戏规则下，两个人都知道石子的堆数和每堆的数量，假设两个人都绝顶聪明而且不会失误，先手的 Alice 是否一定可以必胜？

##### 输入描述: #####

每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n (1 ≤ n ≤ 60) ， 接下来一行有 n 个整数 ai 表示第 i 堆的石子数量( 1 ≤ ai ≤ 1000000000)。

##### 输出描述: #####

如果 Alice 必胜，输出 Alice，否则输出 Bob。
    
     对于样例，Alice 第一步只能拿走第 1 堆上的 1 个石子，接下来 Bob 只要拿走第 2 堆上的全部石子即可获胜。但如果两堆石子数分别是 2 1 ，那么 Alice 就必胜了。

##### 输入例子: #####

2
    1 2

##### 输出例子: #####

Bob

//总结：先分析清楚题目的规律！！！！！----下笔如有神助

package dynamatic;
    
    import java.util.Scanner;
    
    public class D4 {
    	public static void main(String[] args) {
    		Scanner s = new Scanner(System.in);
    		boolean flag = false;// 找规律！！！12大数字前面奇数个1，--bob，偶数个----alice
    		//只输入一次！！
    		while (s.hasNext()) {
    			int n = Integer.parseInt(s.nextLine());
    			int[] a = new int[n];
    			String[] str = s.nextLine().split(" ");
    			int count = 0;
    			int temp = 0;
    			for (int i = 0; i < str.length; i++) {//得到超过1的最早位置
    				if (Integer.parseInt(str[i]) > 1) {
    					temp = i;
    					break;
    				}
    			}
    			for (int j = 0; j < temp; j++) {
    				if (Integer.parseInt(str[j]) == 1) {//统计1的个数
    					count++;
    				}
    			}
    
    			if (count % 2 == 0) {//奇数偶数判断
    				flag = false;
    				break;
    			} else {
    				flag = true;
    				break;
    			}
    
    		}
    
    		if (flag) {
    			System.out.println("Bob");
    		} else {
    			System.out.println("Alice");
    		}
    
    	}
    
    }

**例5：大数问题**

**暴利会栈溢出**

给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。

比如当 x=5，k=1时返回 2，因为5+1=6 不等于 5|1=5，而 5+2=7 等于 5 | 2 = 7。

##### 输入描述: #####

每组测试用例仅包含一组数据，每组数据为两个正整数 x , k。 满足 0 < x , k ≤ 2,000,000,000。

##### 输出描述: #####

输出一个数y。

##### 输入例子: #####

5 1

##### 输出例子: #####

package dynamatic;
    
    import java.util.ArrayList;
    import java.util.Scanner;
    
    public class D5 {
    	public static void main(String[] args) {
    		Scanner s = new Scanner(System.in);
    		while (s.hasNext()) {
    			int x =s.nextInt();
    			int k = s.nextInt();
    			ArrayList<Integer> sArrayList = new ArrayList<>();
    			for (int i = 1; i < 200000000; i++) {
    				if ((x|i) == x+i) {
    					//System.out.println(i);
    					sArrayList.add(i);
    				}
    				
    			}
    			
    			System.out.println(sArrayList.get(k-1));
    			
    	}
    
     }
    }

此题很容易用代码描述，

bool is\_eq(x, y) \{

return x + y == x | y;

然后整个循环从 1 到 y，y 是 第 k 个 满足 is\_eq() 的数。这样做没错，但是 测试用例给整个：

x = 1073741802, k = 1073741823 这么大的数，显然暴力穷举就不合适了。

但是可以举几个数字组合来找其中的规律：

例如：

k = 1 时，5 + 2 == 5 | 2

k = 2 时，5 + 8 == 5 | 8

k = 3 时，5 + 10  == 5 | 10

k = 4 时，5 + 16  == 5 | 16

k = 5 时，5 + 18  == 5 | 18

…

![458841_1465143673189_960CA89CC984A2B1A040CED2998E45D3][]

转二进制

![458841_1465143699386_49FDCDDB8B22BFD4EED8700000FF93E8][]

满足这个运算规律 x + y == x | y 的二进制有：

0 + 0 == 0 | 0

1 + 0 == 1 | 0

1 + 1 !=  1 | 0 (只有这个不满足)

所以 x y 各自相对应的二进制位不能同时为 1，换言之， **x 中 当前位 为 1 时， 与之对应的 y 那一位 肯定是 0**

**所以 x 位为 1 的就确定了，可以去除1**

插入！！！k,除了x为1的位置

![458841_1465143755482_CFBFD3BCEAFFBB2EC17F897B500DBB01][]

![458841_1465143765790_2506AA6EA1512C0DAE9C6353B8273658][]

将 Y 中红色 的 0 去掉看看，得到一组新数据

![458841_1465143810689_157345D231AE030ABE3A8AD43EC31616][]

这正是 从 1 2 3 4 5 6 7，由于 y 表是按照 k 从1递增的顺序得到的值。所以你有理由猜想 这组新数据正是 k ！

X  Y K 之间 有了这个关系，就大胆的编写代码去验证吧。

算法大概是，将 x 和 y 都转成 二进制串， 然后将 y 的二进制串依次塞进 x 串中为 0 的部位，得到的一个新值，

把这个值中原先 x 为 1 的 位 都给改成 0，就能得到 y 值。

比如 k = 3 = b( 1 1), x = 5 = b(0101)

第一步将 k 塞入 x， 得到 b( 11 11)， 第二步将原先 x 中为 1 的变成 0， 得到 b( 10 10) ， 即 y = 10

package dynamatic;
    
    import java.util.*;
    import java.math.BigInteger;
    public class D52{
        public static void main(String args[]){
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){
                int x=sc.nextInt();//5
                int k=sc.nextInt();///1
                StringBuilder res=new StringBuilder();
                String k_bin=Integer.toString(k, 2);//0001
                int index=k_bin.length()-1;
                while(k!=0){
                    if((x&1)==0){//X---0101&0001
                        res.append(k_bin.charAt(index--));//X二进制是1的都变成o,x二进制是0的依次加入k的值
                        k=k>>1;//k的最右位逐步添加到x的0位（右到左）
                    }else{
                        res.append("0");
                    }
                    x>>=1;//无符号右移动
                }
                BigInteger num=new BigInteger(res.reverse().toString(), 2);
                System.out.println(num);
                sc.nextLine();
            }
        }
    }

**例6：马戏团叠罗汉**

搜狐员工小王最近利用假期在外地旅游，在某个小镇碰到一个马戏团表演，精彩的表演结束后发现团长正和大伙在帐篷前激烈讨论，小王打听了下了解到， 马戏团正打算出一个新节目“最高罗汉塔”，即马戏团员叠罗汉表演。考虑到安全因素，要求叠罗汉过程中，站在某个人肩上的人应该既比自己矮又比自己瘦，或相等。 团长想要本次节目中的罗汉塔叠的最高，由于人数众多，正在头疼如何安排人员的问题。小王觉得这个问题很简单，于是统计了参与最高罗汉塔表演的所有团员的身高体重，并且很快找到叠最高罗汉塔的人员序列。 现在你手上也拿到了这样一份身高体重表，请找出可以叠出的最高罗汉塔的高度，这份表中马戏团员依次编号为1到N。

##### 输入描述: #####

首先一个正整数N，表示人员个数。 
    之后N行，每行三个数，分别对应马戏团员编号，体重和身高。

##### 输出描述: #####

正整数m，表示罗汉塔的高度。

##### 输入例子: #####

6
    1 65 100
    2 75 80
    3 80 100
    4 60 95
    5 82 101
    6 81 70

##### 输出例子: #####

package dynamatic;
    
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.Scanner;
    /*
     *
     * 6
       1 65 100
       2 75 80
       3 80 100
       4 60 95
       5 82 101
       6 81 70
     * 
     * 
     * 
     * */
    public class D7 {
        public static void main(String[] args) {
                Scanner sc=new Scanner(System.in);
                while(sc.hasNext()){
                    int n=Integer.parseInt(sc.next());//6
                    int[][] data=new int[n][2];
                    for(int i=0;i<n;i++){
                        int num=Integer.parseInt(sc.next());
                        data[i][0]=Integer.parseInt(sc.next());
                        data[i][1]=Integer.parseInt(sc.next());
                    }
                    dealWith(data);
                }
        }
        public static void dealWith(int[][] data){
            /*
             * sort basing on weight ascending ,if weight the same height descending
             * cause only w1>w2&&h1>h2 || w1==w2&&h1==h2  || w1>w1&&h1=h2 is ok 
             * w1=w2&&h1>h2 isn't ok
             */
             Arrays.sort(data,new Comparator<int[]>(){
                    public int compare(int[] arr1,int[] arr2){
                        if(arr1[0]==arr2[0])//重量相同--比身高--递减排序
                            return arr2[1]-arr1[1];
                        else
                            return arr1[0]-arr2[0];//重量递增排序
                    }
                });
            int[] dp=new int[data.length];//dp记录数组
            for(int i=0;i<data.length;i++){
                dp[i]=1;//初始化
            }
            int max=dp[0];//记录最大值
            //dp算法--典型的两层循环
            for(int i=1;i<data.length;i++){
                for(int j=0;j<i;j++){
                    if(data[i][1]>=data[j][1]&&dp[j]+1>dp[i]){//比较第二列，体重比完--动态比较第二列身高
                            dp[i]=dp[j]+1;
                    }
                }
                if(dp[i]>max)
                    max=dp[i];
            }
            System.out.println(max);
        }
    }

**例7：大数—+FIBO数列**

有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或者二级，要走上m级，共有多少走法？注：规定从一级到一级有0种走法。

给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100。为了防止溢出，请返回结果Mod 1000000007的值。

测试样例：

返回：2

//package dynamatic;
    
    import java.math.BigInteger;
    import java.rmi.registry.Registry;
    import java.util.Scanner;
    
    public class Main {
    
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    		while (in.hasNextInt()) {
    			// 1.初始化
    			BigInteger BigMod = new BigInteger("1000000007");
    			int count = in.nextInt();
    			System.out.println(fibi(count-1).mod(BigMod));
    
    		}
    	}
    
    	private static BigInteger fibi(int count) {
    		BigInteger a = new BigInteger("2");
    		BigInteger b = new BigInteger("1");
    		BigInteger c = new BigInteger("0");
    		BigInteger TEMP1 = new BigInteger("1");
    		BigInteger TEMP2 = new BigInteger("2");
    		//int b =1;
    		//int c =0;
    		if (count==1) {
    			return TEMP1;
    		}
    		if (count == 2) {
    			return TEMP2;
    		}
    		
    		for (int i = 2; i < count; i++) {
    			c = a.add(b);
    			b = a;
    			a = c;
    		}
    		return c;
    		
    	}
    }

**中间处理**

public class GoUpstairs {
      
     // 费波纳西数列的非递归解法
      
      
        public int countWays(int n) {
            // write code here
         if(n==1){return 0;}
          
         long temp1 = 1;
          
         long temp2 = 2;
          
         if(n==2){return 1;}
          
         if(n==3){return 2;}
          
         long  result=0;
          
         for(int i=4;i<=n;i++){
           
          result = (temp1+temp2)%1000000007;
           
          temp1 = temp2%1000000007;
           
          temp2 = result%1000000007;
            
         }
          
         return (int)result;
    1
    2
    3
    4
          
          
        }
    }

**更加简化**

import java.util.*;
      
    public class Main {
        public static void main(String[] args){
            Scanner s = new Scanner(System.in);
            while(s.hasNext()){
                int n = s.nextInt();
                System.out.println(countWays(n));
            }
           
        }
    
        public static int countWays(int n) {
            if(n==1)return 0;
            if(n==2)return 1;
            if(n==3)return 2;
            int[] d=new int[n+1];
            d[1]=0;
            d[2]=1;
            d[3]=2;
            final int MOD=1000000007;
            for(int i=4;i<=n;i++){
                d[i]=(d[i-1]%MOD+d[i-2]%MOD)%MOD;
            }
            return d[n];
        }
    }

**例8：图--航线**

**“呼！！终于到了，可是接下来要怎么走才能到达楚楚街港港呢？”亮亮在醋溜港直发愁。 突然“啾”的一下，一只银色小船出现在亮亮的面前，上面坐着小精灵丹丹“又见面了，有什么可以帮助你的么？”小精灵向亮亮眨了眨眼睛，微笑着说。 “我想去楚楚街港，但我不知道要怎么走，请问你可以告诉我么？”亮亮按捺着激动的心情轻声问道。 “楚楚街港呀......那是个特别美好的地方”小精灵歪着头想了想，说“我只能告诉你大海上所有的航线，剩下的就只能靠你自己啦~” “只有所有的航线呀”，亮亮的内心再三挣扎，却又没有其他的办法。 “不管有多困难，我一定要达到楚楚街港，请你告诉我吧”亮亮坚定地对小精灵说。 小精灵欣赏地点了点头，递给亮亮一张航线图，并叮嘱道“时限是1000天，一定要到哦~”，然后如来时一般“啾”的一声，消失了。 亮亮现在迫切地想要抵达楚楚街港，请问亮亮最快能在第几天抵达楚楚街港呢？**

##### 输入描述: #####

一行包含两个整数N(2<=N<=500),M(1<=M<=2000)，用单个空格隔开。表示公有N个港，M条航线，起点为1，终点为N。
    接下来M行，每行包含五个整数P,Q(1<=P,Q<=n), K(1<=K<=1000), X,Y(0<=X,Y<=10000),代表P,Q两个港有航线并需要K天，并且该航线在第X天到第Y天天气恶劣不可通行。

##### 输出描述: #####

一个整数，即亮亮最快能在第几天抵达楚楚街港

##### 输入例子: #####

4 4
           
    2 1 1 7 13
    
    4 3 2 10 11
    
    1 3 8 9 12
    
    2 3 3 2 10

##### 输出例子: #####

package dynamatic;
    
    import java.util.Scanner;
    
    public class D10航行图路径 {
    	public final static int MAX_K = 1001;
    
    	/**
    	 *
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner s = new Scanner(System.in);
    		while (s.hasNext()) {
    			int n = s.nextInt();// N个顶点
    			int m = s.nextInt();// M条边。下面都多用一个位置，下标从1开始
    			int[][] graph = new int[n + 1][n + 1];// 保存图
    			int[][] start = new int[n + 1][n + 1];// 恶劣天气的开始天数
    			int[][] end = new int[n + 1][n + 1];// 恶劣天气的结束天数
    			int[] shortDis = new int[n + 1];// 记录从1到各个顶点的最短距离
    			int[] visited = new int[n + 1];// n个顶点访问标记，默认都是0未访问
    			/**
    			 * 任意两个点之间的距离初始化为无穷大
    			 */
    			for (int i = 1; i <= n; i++) {
    				for (int j = 1; j <= n; j++) {
    					if (i != j) {
    						graph[i][j] = MAX_K;
    					}
    				}
    			}
    			/**
    			 * 接着有m行输入
    			 */
    			for (int i = 0; i < m; i++) {
    				int p = s.nextInt();
    				int q = s.nextInt();
    				int k = s.nextInt();
    				int x = s.nextInt();
    				int y = s.nextInt();
    				graph[p][q] = graph[q][p] = k;
    				start[p][q] = start[q][p] = x;
    				end[p][q] = end[q][p] = y;
    			}
    
    			/**
    			 * 初始化1到其它顶点的最短距离
    			 */
    			for (int i = 2; i <= n; i++) {
    				// 这里要用自定义的距离公式
    				shortDis[i] = delay(0, graph[1][i], start[1][i], end[1][i]);
    			}
    			/******* 初始化结束 *********/
    			visited[1] = 1;// 标记顶点1已经被访问过了
    			int min, v = 1;// 当前最短距离min和对应的顶点号
    			// 这里应该是，将顶点1标记为已经访问，
    			// 考察当所有已经被访问的顶点为前一个点，到达考察点的距离，找到这些中的最小距离；就是该点的最小距离
    			for (int i = 2; i <= n; i++) {// 遍历所有
    				for (int j = 1; j <= n; j++) {
    					for (int k = 1; k < i; k++) {
    						if (j != k) {
    							int disij = delay(shortDis[k], graph[k][j], start[k][j], end[k][j]);
    							if (shortDis[j] > disij) {
    								shortDis[j] = disij;
    							}
    						}
    					}
    				}
    			}
    			// for(int i=1;i<=n;i++){
    			// System.out.println("1"+">"+i+":"+shortDis[i]+" ");
    			// }
    			System.out.println(shortDis[n]);
    		}
    	}
    
    	/**
    	 * 因为恶劣天气影响的延时
    	 * 
    	 * @param now
    	 * @param length
    	 * @param start
    	 * @param end
    	 * @return
    	 */
    	public static int delay(int now, int length, int start, int end) {
    		if (length == MAX_K) {
    			return length;
    		}
    		/**
    		 * 在恶劣天气区间外的情况可以直接通行,否则要等待到天气转好
    		 */
    		if (now + length < start || now >= end + 1) {
    			return now + length;
    		}
    		return end + 1 + length;
    	}
    
    }

9.股票交易

在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于2)，规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列，请写一个程序计算一天可以获得的最大收益。请采用实践复杂度低的方法实现。

给定价格序列prices及它的长度n，请返回最大收益。保证长度小于等于500。

测试样例：

[10,22,5,75,65,80],6

返回：87

package dynamatic;
    
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.Set;
    import java.util.TreeMap;
    
     
    public class D11炒股最大收益 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            Set<String> set = new HashSet<>();
            int max1 = 0;//最大差
            while (sc.hasNextLine()) {   
               String temp = sc.nextLine();
               int n = Integer.parseInt(temp.substring(temp.length()-1));
               int numlast = temp.indexOf("]");
               int numfirst = temp.indexOf("[");
               String num = temp.substring(numfirst+1, numlast);
               String[] strNum = num.split(",");
               int[] tempstr = new int[n];
               for (int i = 0; i < strNum.length; i++) {
    			 tempstr[i]=Integer.parseInt(strNum[i]);
    		}
       
               System.out.println( maxProfit(tempstr, n));
               System.out.println( maxProfit2(tempstr));
               System.out.println( maxProfit3(3,tempstr));
     
            }
            
          
        }
    //----------------------------
        
        public static int maxProfit2(int[] prices) {
            int min = Integer.MAX_VALUE, res = 0;
            for(int i = 0 ; i < prices.length; i++){
                if(prices[i]<min) min = prices[i];
                if((prices[i]-min)>res) res = prices[i] - min;
            }
            return res;
        }
        
        //---------------动态规划---抛售k次的最大收益
        public static int maxProfit3(int k, int[] prices) {
            if(prices.length == 0) return 0;
            //用II的解法优化k > prices.length / 2的情况
            if(k > prices.length / 2){
                int sum = 0;
                for(int i = 1; i < prices.length; i++){
                    if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1];
                }
                return sum;
            }
            //初始化全局变量和局部变量
            int[][] global = new int[prices.length][k+1];
            int[][] local = new int[prices.length][k+1];
            for(int i = 1; i < prices.length; i++){
                int diff = prices[i] - prices[i-1];
                for(int j = 1; j < k + 1; j++){
                    //更新局部变量
                    local[i][j] = Math.max(global[i-1][j-1]+Math.max(0, diff), local[i-1][j]+diff);
                    //更新全局变量
                    global[i][j] = Math.max(global[i-1][j], local[i][j]);
                }
            }
            return global[prices.length - 1][k];
        }
        
        
        
        
        
        
        public static int maxProfit(int[] prices, int n) {
            if (n==0){ return 0; }
            int[] left = new int[n];
            int[] right= new int[n];
            int leftMin=prices[0];
            int rightMax=prices[n-1];
            int sum = 0;
            //prices[0]到prices[i]的最大收益应该:
            // 当前卖出能获得的最大收益 和 prices[0]到prices[i-1]的最大收益中
            // 二者较大的那个。
            //分别得出以i点为分割点，左半段最大收益的数组left，和右半段最大收益的数组right后.
            //我们就可以遍历一遍这两个数组，找出最大的left+right组合。
            for(int i = 1 ; i<n ; i++){
               leftMin = Math.min(prices[i],leftMin);//两个数相比较
               left[i] = Math.max(prices[i]-leftMin , left[i-1]);
            }
            for(int i = n-2 ; i>=0 ;i--){
                rightMax = Math.max(prices[i],rightMax);
                right[i] = Math.max(rightMax-prices[i] , right[i+1]);
            }
            for(int i = 0 ;i<n ;i++){
                 if((left[i]+right[i])>sum) sum = left[i]+right[i];
            }
            return sum;
        }
    }

[458841_1465143673189_960CA89CC984A2B1A040CED2998E45D3]: /images/20220719/1eb355d3022040d38f328321faf66f1d.png
[458841_1465143699386_49FDCDDB8B22BFD4EED8700000FF93E8]: /images/20220719/f368797bda694a1091a8e9dd3fecd8bf.png
[458841_1465143755482_CFBFD3BCEAFFBB2EC17F897B500DBB01]: /images/20220719/b4e23afc086849e89879dcb5a6d262ee.png
[458841_1465143765790_2506AA6EA1512C0DAE9C6353B8273658]: /images/20220719/4eb7ae88afeb4d4696ab823158a93549.png
[458841_1465143810689_157345D231AE030ABE3A8AD43EC31616]: /images/20220719/ce298c2d552c4a1b85aa82154dc09525.png