在本教程中，我们将研究最长的递增子序列，并使用动态编程来解决。
问题陈述：
给你一个整数数组；您需要找到最长的递增子序列。
这意味着，您需要找到一个排序后的子数组，其总和为max。
例：
输出：
这里的长度是4。
这里1、2、5、8在数组中按排序顺序。
还有3、8。但是总和较少。
因此，我们将在动态编程的帮助下解决此示例。
我们将采用以下临时数组
至少现在，每个索引的最长子序列可以为1。因为，如果数组中没有递增的子序列，则每个索引本身都可以是一个子序列。
因此，我们最初在所有索引处用全1填充了DP数组。
为了解决这个问题，我们采用2个变量“ i”和“ j”。其中“ i”从索引[1]开始，“ j”从0开始至“ i”。
现在，我们检查array [j]上的值是否小于array [i]上的值，然后在DP表中执行一个操作，然后递增索引“ j”。
如果arr [j]的值大于arr [i]的值，则我们不对DP数组执行任何操作，只需增加索引“ j”即可。
当“ j”和“ i”达到相同的索引时，我们将“ i”值递增以指向下一个元素，并将“ j”值重置为0。
再一次，我们继续上一步。
我们将借助一个例子来理解这一点。
通行证1：
初始“ i”和“ j”值如下所示
在此，“ j”为i以上。因此增加“ j”。但是，“ i”和“ j”在同一索引中。因此，我们将“ j”重置为0并增加“ i”值，如下所示：
现在是arr [j]<arr [i]。因此，在dp [i]处最长的递增子序列将是dp [j] +1。
因此它将是dp [2] = dp [0] + 1
dp [2] = 1 +1
dp [2] = 2
现在增加“ j”值。现在也是arr [j]< arr[i].
因此dp [i] = dp [j] +1
= 1 + 1
现在增加“ j”，现在“ i”和“ j”的索引都相同。因此，将“ i”增加1并将j值重置为0。
现在是arr [j]is not less than arr[i]. Hence increment “j”.
现在是arr [j]<arr [i]。因此dp [i] = dp [j] +1
= 1 + 1 = 2
增量j。现在arr [j] = 6且arr [i] =2。arr [j]不小于arr [i]。因此增加“ j”。现在，“ i”和“ j”处于相同的索引。递增“ i”值，将j值重置为0。
现在arr [j] = 3 ad arr [i] = -1，这不少。同样，所有值都大于arr [i]。因此，我们在此阶段不执行任何操作。
下一遍将开始，如下所示：
如果观察PD阵列，它将始终显示最长增加子序列，直到该索引为止。
现在是arr [j]= 3 and arr[i] = 5. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 1 + 1 = 2
同样，arr [j] = 1且arr [i] =5。它小于arr [i]。因此，更新DP阵列。
dp [i] = dp [j] + 1
= 1 + 1 = 2
同样，arr [j] = 6和arr [i] =5。它大于arr [i]。递增“ j”索引。
同样，arr [j] = 2和arr [i] =5。它小于arr [i]。因此，更新DP阵列。
dp [i] = dp [j] + 1
= 2 + 1 = 3
同样，arr [j] = -1和arr [i] =5。它小于arr [i]。因此，更新DP阵列。
dp [i] = dp [j] + 1
= -1 + 1 = 0
这里我们取最大值[2，2，3，0]。最大值为“ 3”。
在传递结束时，DP阵列将如下所示：
再次进行下一次遍历，变量将如下所示：
现在是arr [j]= 3 and arr[i] =4. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 1 + 1 = 2
现在是arr [j]= 1 and arr[i] =4. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 1 + 1 = 2
现在arr [j] = 6和arr [i] = 4。大于arr [i]。不执行任何操作，将索引“ j”递增。
现在是arr [j]= 2 and arr[i] =4. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 2 + 1 = 3
现在是arr [j]= -1 and arr[i] =4. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 1 + 1 = 2
现在arr [j] = 5和arr [i] = 4。大于arr [i]。不执行任何操作，将索引“ j”递增。
在此过程结束时，DP阵列将如下所示：
在下一遍的开始，要点如下：
现在是arr [j]= 3 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 1 + 1 = 2
现在是arr [j]= 1 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 1 + 1 = 2
现在是arr [j]= 6 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 2 + 1 = 3
现在是arr [j]= 2 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 2 + 1 = 3
现在是arr [j]= -1 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= -1 + 1 = 0
现在是arr [j]= 5 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 3 +1 = 4
现在是arr [j]= 4 and arr[i] = 8. Which is less than arr[i]. Hence update DP array.
dp [i] = dp [j] + 1
= 3 +1 = 4
最大值是4，因此是我们的结果。
C ++解决方案
#include<iostream>
using namespace std;
int dp_function( int arr[], int n )
{
int dp_array[n];
dp_array[0] = 1;
for (int i = 1; i < n; i++ )
{
dp_array[i] = 1;
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] && dp_array[i] < dp_array[j] + 1)
dp_array[i] = dp_array[j] + 1;
}
return *max_element(dp_array, dp_array+n);
}
int main()
{
int arr[] = { 3, 1, 6, 2, -1, 5, 4, 8 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of Longest Increasing Subsequence is %d\n", dp_function( arr, n ) );
return 0;
}
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
