Longest Increasing Continuous Subsequence I

Give an integer array，find the longest increasing continuous subsequence in this array.

An increasing continuous subsequence:

• Can be from right to left or from left to right.
• Indices of the integers in the subsequence should be continuous.

Notice

O(n) time and O(1) extra space.

Example

For[5, 4, 2, 1, 3], the LICS is[5, 4, 2, 1], return4.

For[5, 1, 2, 3, 4], the LICS is[1, 2, 3, 4], return4.

Analysis

Since the increasing subsequence can go from right to left or left to right, it's tempting to use array to store the maximum subsequence for each element. However, it violates the O(1) extra space restriction although with memorization, O(n) time is still possible. After writing dp and memorization for a while, pay attention to questions as such because dp is not required. Two loops one from left to right and another from right to left, looking for the maximum continuous subsequence should be sufficient for the solution.

Solution

 public int longestIncreasingContinuousSubsequence(int[] A) {
    if (A.length == 0) {
        return 0;
    }
    int ans = 1;
    int length = 1;
    for (int i = 0; i < A.length - 1; i++){
        if (A[i] > A[i+1]){
            length++;
        } else {
            ans = Math.max(ans, length);
            length = 1;
        }
    }

    ans = Math.max(ans, length);

    length = 1;
    for (int i = A.length - 1; i > 0; i--){
        if (A[i] > A[i-1]){
            length++;
        } else {
            ans = Math.max(ans, length);
            length = 1;
        }
    }

    ans = Math.max(ans, length);

    return ans;
 }

Longest Increasing Continuous Subsequence II

Give you an integer matrix (with row size n, column size m)，find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).

Example

Given a matrix:

[
  [1 ,2 ,3 ,4 ,5],
  [16,17,24,23,6],
  [15,18,25,22,7],
  [14,19,20,21,8],
  [13,12,11,10,9]
]

return 25

Challenge

O(nm) time and memory.

Analysis

The first question is how to find the start position. Since any point can be a start position, we need to loop over the matrix for each position as a start position. To achieve O(nm), memorization is necesary. The technique is called memoerization search. This is a special type of DP, with the 4 properties, state, function, initialization and answer. Using dp matrix to store the state, function being the dx, dy traversal of the each pos, initilization being the dp[x,y] = 1 to start with, and answer is the maximum value in all dp matrix. Note that Memorization search requires O(nm) time and memory space.

When to use Memorizatoin search: the initial state is different to find: therefore it required a complete loop over all the elements in the matrix and state transformation is not ordered. for example, dx, dy can be in 4 directions in this case.

Solution

int [] dx = {1, -1, 0, 0};
int [] dy = {0, 0, -1, 1};

int[][] dp = null;
boolean[][] flag = null;

public int longestIncreasingContinuousSubsequenceII(int[][] A) {
    if (A.length == 0 || A[0].length == 0){
        return 0;
    }

    dp = new int[A.length][A[0].length];
    flag = new boolean[A.length][A[0].length];

    int ans = 0;
    for (int i = 0; i < A.length; i++){
        for (int j = 0; j < A[0].length; j++){
            dp[i][j] = search(A, i, j);
            ans = Math.max(ans, dp[i][j]);
        }
    }
    return ans;
}

public int search(int[][] A, int i, int j){
    if (flag[i][j]){
        return dp[i][j];
    }

    dp[i][j] = 1;
    for (int k = 0; k < dx.length; k++){
        int nx = i + dx[k];
        int ny = j + dy[k];

        if (nx >= 0 && nx < A.length && ny >= 0 && ny < A[0].length){
            if (A[i][j] > A[nx][ny]){
                dp[i][j] = Math.max(dp[i][j], search(A, nx, ny) + 1);
            }
        }
    }

    flag[i][j] = true;
    return dp[i][j];
}