编写题解 1557: 蓝桥杯算法提高VIP-聪明的美食家

解题思路:

注意事项:
其实就是 当前的美食甜度  与  前面的美食的甜度 的比较

因为最少可以爽一次所以设置d[]全部为一，反正也是设置arr[]顺路的，然后再来个最大max用来比较d[]

再双for分别指向前一个以及后一个，相互比较，如果满足条件那么就d[i]+1，别忘了如果比max大那就的赋值给他。

（看着图来理解一下，自己动手画一下最好）

package DP;
import java.util.Scanner;
 
public class T1557聪明的美食家 {
 
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] arr = new int[n];
		int[] d = new int[n];
		for(int i=0;i<n;i++){
			arr[i] = scanner.nextInt();
			d[i]=1;
		}
		int max = 0;
		for(int i=1;i<n;i++){
			for(int j=i-1;j>=0;j--){
				if(arr[i]>=arr[j]){	//等于是为了都是1的情况
					d[i]=Math.max(d[i], d[j]+1);    //arr[j]+1指包括了arr[i]
					if(d[i]>max){
						max=d[i];
					}
				}
			}
		}
		System.out.println(max);
	}
 
}

参考代码: