在本教程中,我们将研究最长的递增子序列,并使用动态编程来解决。
问题陈述:
给你一个整数数组;您需要找到最长的递增子序列。
这意味着,您需要找到一个排序后的子数组,其总和为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+章 |