题解 | #最长上升子序列(一)#
最长上升子序列(一)
https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f
int max(int a,int b)
{
if(a > b)
return a;
return b;
}
int LIS(int* arr, int arrLen )
{
// write code here
if(arrLen == 0)
return 0;
int dp[arrLen];//用dp[i]表示到数组元素下标为i的元素作为结尾时,最长的上升子序列的长度
for(int i = 0;i < arrLen;i++)//,初始化为1,因为只有数组有元素,至少有一个算是递增。
{
dp[i] = 1;
}
for(int i = 0;i < arrLen;i++) //获得以数组的每个元素为上升序列的结尾的序列长度
{
for(int j = 0;j < i;j++)
{
if(arr[j] < arr[i])//对应每个以arr[i]结尾的上升子序列,如果在它之前遇到比arr[i]更小的arr[j]
{
dp[i] = max(dp[i], dp[j] + 1);//那么上升子序列的长度可以为dp[j]+1,但是要取两者的最大值
}
}
}
int max = 1;
for(int i = 0;i < arrLen;i++)
{
if(dp[i] > max)
max = dp[i];
}
return max;
}
{
if(a > b)
return a;
return b;
}
int LIS(int* arr, int arrLen )
{
// write code here
if(arrLen == 0)
return 0;
int dp[arrLen];//用dp[i]表示到数组元素下标为i的元素作为结尾时,最长的上升子序列的长度
for(int i = 0;i < arrLen;i++)//,初始化为1,因为只有数组有元素,至少有一个算是递增。
{
dp[i] = 1;
}
for(int i = 0;i < arrLen;i++) //获得以数组的每个元素为上升序列的结尾的序列长度
{
for(int j = 0;j < i;j++)
{
if(arr[j] < arr[i])//对应每个以arr[i]结尾的上升子序列,如果在它之前遇到比arr[i]更小的arr[j]
{
dp[i] = max(dp[i], dp[j] + 1);//那么上升子序列的长度可以为dp[j]+1,但是要取两者的最大值
}
}
}
int max = 1;
for(int i = 0;i < arrLen;i++)
{
if(dp[i] > max)
max = dp[i];
}
return max;
}