Hashmat is a brave warrior who with his group of young soldiers moves from one place to another to fight against his opponents. Before fighting he just calculates one thing, the difference between his soldier number and the opponent's soldier number. From this difference he decides whether to fight or not. Hashmat's soldier number is never greater than his opponent.
Longest Increasing SubsequenceAccording to Arefin bookInput: Given a sequenceOutput: The longest subsequence of the given sequence such that all values in thislongest subsequence is strictly increasing/decreasing.O(N^2) DP solution for LIS problem (this code check for increasing values):
for i = 1 to total-1for j = i+1 to totalif height[j] > height[i] thenif length[i] + 1 > length[j] thenlength[j] = length[i] + 1predecessor[j] = iExample of LISheight sequence: 1,6,2,3,5length initially: [1,1,1,1,1] - because max length is at least 1 rite...predecessor initially: [nil,nil,nil,nil,nil] - assume no predecessor so far
After first loop of j:length: [1,2,2,2,2], because 6,2,3,5 are all > 1predecessor: [nil,1,1,1,1]After second loop of j: (No change)length: [1,2,2,2,2], because 2,3,5 are all < 6predecessor: [nil,1,1,1,1]After third loop:length: [1,2,2,3,3], because 3,5 are all > 2predecessor: [nil,1,1,3,3]After fourth loop:length: [1,2,2,3,4], because 5 > 3predecessor: [nil,1,1,3,4]