题解 | #Redraiment的走法#
Redraiment的走法
http://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa
给出两种方法 第一种300ms 太那啥了
#include<stdio.h>
#include<stdlib.h>
int max = 1;
void solu(int arr[],int step,int value,int idx,int n){
int f = 0;
for(int i=idx;i<n;i++){
if(arr[i]>value){
solu(arr,step+1,arr[i],i+1,n);
f = 1;
}
}
if(f==0){
if(step>max)
max = step;
}
}
int main(){
int n;
scanf("%d",&n);
int*arr = (int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
// 方法1 dfs - 300ms ---
// int step = 0;
// int value = 0;
// int idx = 0;
// solu(arr,step,value,idx,n);
// printf("%d",max);
// free(arr);
// 方法2 类似 合唱队 从左往右的最大升序
int*lmax = (int*)malloc(sizeof(int)*n);
for(int i=0;i<n;i++) lmax[i] = 1;
int max = 1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(arr[j]<arr[i] && lmax[j]==lmax[i]){ //在j左侧有都有相同的序列
lmax[i] = lmax[j]+1;
if(lmax[i]>max)
max = lmax[i];
}
}
}
printf("%d",max);
}
美的集团公司福利 300人发布
查看21道真题和解析