题目描述
小明是蓝桥王国的勇士，他晋升为蓝桥骑士，于是他决定不断突破自我。
这天蓝桥首席骑士长给他安排了 NN 个对手，他们的战力值分别为 a1,a2,...,ana1,a2,...,an，且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。
作为热血豪放的勇士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。
请你算算小明最多会挑战多少名对手。
输入描述
输入第一行包含一个整数 NN，表示对手的个数。
第二行包含 NN 个整数 a1,a2,...,ana1,a2,...,an，分别表示对手的战力值。
1≤N≤1031≤N≤103，1≤ai≤1091≤ai≤109。
输出描述
输出一行整数表示答案。
输入输出样例
示例
输入
6
1 4 3 2 5 6
输出
4
解题思路
1. a[] 数组：保存每个对手的战力数值。
2. count[] 数组： count[i] 代表以第i个对手作为队伍最后一人，能选出的最长队伍人数。
3. 初始化：每一个人最少只选自己，所以 count[i] = 1 。
4. 双层循环：
外层i：依次处理每一个人。
内层j：遍历i前面所有人。
第一个if： a[i]>a[j] ，i的战力更大，可以接在j的队伍后面，就进入开始计算。
第二个if： count[j]+1 > count[i] ，只有拼接后的队伍更长，才更新count[i]。
5. 最后遍历count数组，找到里面最大值，就是答案。
完整代码
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int n;
int a[1024];
int count[1024];
scanf("%d",&n);
int i,j;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
count[i]=1;
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[i]>a[j])
{
if(count[j]+1>count[i])
{
count[i]=count[j]+1;
}
}
}
}
int max=0;
for(i=0;i<n;i++)
{
if(count[i]>max)
{
max=count[i];
}
}
printf("%d\n",max);
return 0;
}
踩坑记录
1. 致命错误：最后求最大值的时候，错误读取 a数组 。a存的是战力， count数组才存队伍长度，必须遍历count数组找最大值。
2. 数组开太小，我一开始写a[512] ，测试数据n超过512，数组越界，直接超时。LV1题目没有写明n上限，数组直接开大点预留空间。
3. 分不清贪心和DP：
连续一段（子串）→单层循环贪心
可以跳过元素（子序列）→必须DP双层循环，简单贪心会算错
4. 第二个if理解难点：同一个i，前面会有很多j，每一个j会算出一个队伍长度。第二个if：只有新队伍比当前记录更长，才更新count[i]，不允许短的队伍覆盖已经找到的最长方案。
5. 初始化 count[i]=1，每个人最少可以单独成队
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2402_87421821/article/details/169458524
