[ALGORITHM] LIS
LIS(Longest increasing Subsequence
最大増分部分数列
「前」->「後」の数字を選択すると、「均一な部分」列の長さを最大限に延長し、数値順に増加します.
例えば、配列{6,2,5,1,7,4,8,3}がある場合、LISは{2,5,7,8}である
{2,5,{2,7}などの増分部分の数列が多いが,その中で最も長いのは{2,5,7,8}である.
DP O(N*N), O(lonN)
DPO(N*N)方法
length[i]は、iインデックスに終了する最大インクリメンタル部分列の長さである.
内部反復文を使用してk未満のインデックスを1つずつ表示し、arr[i]
最大増分部分数列
「前」->「後」の数字を選択すると、「均一な部分」列の長さを最大限に延長し、数値順に増加します.
例えば、配列{6,2,5,1,7,4,8,3}がある場合、LISは{2,5,7,8}である
{2,5,{2,7}などの増分部分の数列が多いが,その中で最も長いのは{2,5,7,8}である.
DP O(N*N), O(lonN)
DPO(N*N)方法
length[i]は、iインデックスに終了する最大インクリメンタル部分列の長さである.
内部反復文を使用してk未満のインデックスを1つずつ表示し、arr[i]
for (int k = 0; k < n; k++){
length[k] = 1;
for (int i = 0; i < k; i++){
if(arr[i] < arr[k]){
length[k] = max(length[k], length[i] + 1);
}
}
}Reference
この問題について([ALGORITHM] LIS), 我々は、より多くの情報をここで見つけました https://velog.io/@redcarrot01/알고리즘-LISテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol