{"id":26502,"date":"2017-12-20T21:26:00","date_gmt":"2017-12-20T15:56:00","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26502"},"modified":"2017-12-20T21:26:00","modified_gmt":"2017-12-20T15:56:00","slug":"variations-of-lis","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/variations-of-lis\/","title":{"rendered":"Variations of LIS"},"content":{"rendered":"<p>We have discussed Dynamic Programming solution for Longest Increasing Subsequence problem in this post and a O(nLogn) solution in this post. <span id=\"more-19255\"><\/span>Following are commonly asked variations of the standard LIS problem.<\/p>\n<ul>\n<li><strong>Building Bridges: <\/strong>Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a(1) \u2026 a(n) and n cities on the northern bank with x-coordinates b(1) \u2026 b(n). You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city i on the northern bank to city i on the southern bank.<\/li>\n<\/ul>\n<pre>8     1     4     3     5     2     6     7  \r\n&lt;---- Cities on the other bank of river----&gt;\r\n--------------------------------------------\r\n  &lt;--------------- River---------------&gt;\r\n--------------------------------------------\r\n1     2     3     4     5     6     7     8\r\n&lt;------- Cities on one bank of river-------&gt;<\/pre>\n<ul>\n<li><strong>Maximum Sum Increasing Subsequence:<\/strong> Given an array of n positive integers. Write a program to find the maximum sum subsequence of the given array such that the intgers in the subsequence are sorted in increasing order. For example, if input is {1, 101, 2, 3, 100, 4, 5}, then output should be {1, 2, 3, 100}. The solution to this problem has been published here.<\/li>\n<\/ul>\n[ad type=&#8221;banner&#8221;]\n<ul>\n<li><strong>The Longest Chain<\/strong> You are given pairs of numbers. In a pair, the first number is smaller with respect to the second number. Suppose you have two sets (a, b) and (c, d), the second set can follow the first set if b &lt; c. So you can form a long chain in the similar fashion. Find the longest chain which can be formed. The solution to this problem has been published here.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<ul>\n<li><strong>Box Stacking<\/strong> You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.<\/li>\n<\/ul>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Variations of LIS &#8211; Dynamic Programming &#8211; We have discussed Dynamic Programming solution for Longest Increasing Subsequence problem in this post<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83519,83508,70145,80127],"tags":[78975,78976,78970,72847,72842,72845,70483,72848,72840,72846,72987,78974,72843,72992,72854,72844,78972,72850,72839,78973,72852,72855,78971,72853,78969,72851],"class_list":["post-26502","post","type-post","status-publish","format-standard","hentry","category-closest-pair","category-cycle-sort","category-dynamic-programming","category-heap","tag-box-stacking-problem-dynamic-programming","tag-building-bridges-code","tag-building-bridges-problem","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-java","tag-dynamic-programming-practice-problems","tag-dynamic-programming-problems","tag-dynamic-programming-python","tag-dynamic-programming-set-1","tag-dynamic-programming-software","tag-dynamic-programming-type","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-longest-increasing-subsequence-using-dynamic-programming","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-tutorial-for-dynamic-programming","tag-types-of-dynamic-programming","tag-variations-of-lis","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26502","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26502"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26502\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26502"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26502"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26502"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}