登录
  • #刷题

us‌‌‍‍‌‍‍‌‍‌‍‍‌‍‍‍‌‌‌‍‌‌‌‍‌‍‍‍‌‍‍‌e divide and conquer to solve Longest Increasing Subsequence problem

hanrui_542
1854
0
Longest Increasing Subsequence 最常见的就是用Dynamic Programming,通常用这个recurrence relation:A(i) = 1 + max{A(j)| 1 ≤ j < i and a_j < a_i}. 用divide and conquer方法在写recurrence relation的时候不同,要首先假设a是LIS中的一员,for all the i, recursively solve the right and left side of a, find the longest one. 第一眼貌似挺好写的,可是问题是怎么track the largest element in the left part LIS and the smallest element in the right part LIS.
0条回复
热度排序

发表回复