合唱队
合唱队
http://www.nowcoder.com/questionTerminal/6d9d69e3898f45169a441632b325c7b4
dp1[i]为最后一项是i的递增序列最多有多少人
dp2[i]为最后一项是i的符合合唱队的序列有多少人(有可能身高递增也可能先增再减)
dp2[i][j]为最后一个人是i倒数第二个人是j时序列最多有多少人(j∈(0,i-1)
若身高[i]<身高[j] dp2[i][j]=1+dp2[j];
若身高[i]>身高[j] dp2[i][j]=1+dp1[j];
则dp2[i]=max(dp2[i][j])
然后答案就是输出n-max(dp2[i])
投递快手等公司10个岗位
