Longest Common Sub-Sequence

The longest common subsequence (LCS) problem is very popular in computer science. This problem can be solved by dynamic algorithm. We can define this problem to find the longest subsequence common to all sequences in a set of sequences (often just two sequences).

Let A  = {1,3,4,6,8}
B = {7, 3,2,4,6,10,8}

LCS (A,B) = {3,4,6,8} , Length = 4;

Longest Decreasing Subsequence

Read : Longest Increasing Subsequence
Dynamic Programming:

Longest Increasing Subsequence

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. he longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence.
Example:
In the first 16 terms of the binary Van der Corput sequence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

a longest increasing subsequence is

0, 2, 6, 9, 11, 15.

This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,

0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15

are other increasing sub sequences of equal length in the same input sequence [Wiki].
Dynamic Problem:

Maximum Subarray Problem

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. A linear time algorithm was found soon afterwards by Jay Kadane of Carnegie-Mellon University (Bentley 1984). [Wiki]

Example:
[1] A = {-2,1,-1,1,1,-1,2,1,-5}; [assum, 1st element is indicated by 0]
Maximum Value = 4, start index = 1, End index = 7

[2] A = {-2,1,-2,1,1,-1,2,1,-5}; [assum, 1st element is indicated by 0]
Maximum Value = 4, start index = 3, End index = 7

[3] A = {-2,1,-3,4,-1,2,1,-5,-4}; [assum, 1st element is indicated by 0]
Maximum Value = 6, start index = 3, End index =6

[4] A = {2,3,5,4,6,3,5,4,6};
Maximum Value = 38, start index = 0, End index =8

[5] A = {-1,-2,-3,-4,-5,-6,-7,-8,-9}
Maximum Value = -1, start index = 0, End index =0