1

enter image description here

I've been working on this problem for awhile and couldn't come up with the solution; I hope you can help out..

I'm trying to find the longest increasing sequence of numbers. For example, if I have the following 4X4 array:

[![enter image description here][1]][1]

    int [] nums = {
        {97 , 47 , 56 , 36},
        {35 , 57 , 41 , 13},
        {89 , 36 , 98 , 75},
        {25 , 45 , 26 , 17}
    };

THE EXPECTED RESULT : return 8 and the LIS 17, 26, 36, 41, 47, 56, 57, 97 I don't have the answer to it yet, I'm trying to reach it.

17  (3,3)
26  (3,2)
36  (2,1)
41  (1,2)
47  (0,1)
56  (0,2)
57  (1,1)
97  (0,0)

I hope my example is clear enough..

This is my code; when I try to find the longest increasing path, it doesn't do it backward not diagonally. Can anyone help me please?

public class Solution2 {
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    public static int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0)
            return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dis = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dfs(i, j, m, n, matrix, dis));
            }
        }
        return ans;
    }

    static int dfs(int x, int y, int m, int n, int[][] matrix, int[][] dis) {
        if (dis[x][y] != 0)
            return dis[x][y];

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < m && ny < n && matrix[nx][ny] > matrix[x][y]) {
                dis[x][y] = Math.max(dis[x][y], dfs(nx, ny, m, n, matrix, dis));
            }
        }
        return ++dis[x][y];
    }

    public static void main(String[] args) {
        int arr[][] = { 
          { 97, 47, 56, 36 }, 
          { 35, 57, 41, 13 }, 
          { 89, 36, 98, 75 }, 
          { 25, 45, 26, 17 }
        };
        System.out.println(longestIncreasingPath(arr));
    }
}
Al-otaibi Ayman
  • 51
  • 8
  • 1
    I don't understand what you are trying to do. You listed a longest sequence that is not in the array you provided; I don't even see a relationship between your answer and your data. Where did this longest sequence come from? – R. Barzell Oct 14 '17 at 03:54
  • 2
    Your example is not clear to me how it will return 8 ? – Lokesh Pandey Oct 14 '17 at 03:54
  • 17-> 26->36->41-> 47->56-> 57-> 97 it goes from the bottom right of the array, and goes up.. I added the coordinate on the example.. – Al-otaibi Ayman Oct 14 '17 at 04:05
  • Let me try it in my words: you are looking for a path in the matrix where you can step from one cell to a neighbouring cell. – Henry Oct 14 '17 at 04:13
  • @Lokesh you are free to choose the first cell and you can go to a neighbouring cell if the number is bigger. Make your choices in such a way, that the path has maximum length. – Henry Oct 14 '17 at 04:18
  • the result 8 is what to be expect. I did not get it yet. that's the assignment... Secondly, yes Henry, moving in all direction, and looking for the longest increasing path – Al-otaibi Ayman Oct 14 '17 at 04:18
  • Nice challenge bro, you will need to find all sequences and test all of then – Marcos Vasconcelos Oct 14 '17 at 04:26
  • @Henry ok. it's a good challenge – Lokesh Pandey Oct 14 '17 at 04:26
  • yeah, and the prof gave us a hint, he said use Stack, haha that's all.. – Al-otaibi Ayman Oct 14 '17 at 04:30
  • @Henry It's a dp problem. Don't you think `O(n*m*log(n*m))` is bit expensive complexity ? – Lokesh Pandey Oct 14 '17 at 04:31
  • it sounded very complicated.. I'm no where near the solution I guess.. – Al-otaibi Ayman Oct 14 '17 at 04:31
  • @Lokesh well, to look at each number once will already take `O(n*m)` so it is not that much. The log part comes from the sorting to make DP work. Do you have a faster method? – Henry Oct 14 '17 at 04:33
  • 1
    Isn't this an NP-hard problem? This is basically looking for a Hamiltonian path in a graph such that edges go from x to y if you can move from x to y (so they're adjacent in the matrix) _and_ x < y. The job is to find the longest path, which is an NP-hard problem. It can be solved with various methods in some _reasonable_ time, but for arbitrary matrices it cannot be solved in polynomial time unless P = NP. – Gergely Kőrössy Oct 14 '17 at 04:45
  • @GergelyKőrössy two observations: 1) we don't necessarily visit each vertex (therefore it is not a hamiltonian path). 2) the order of the vertices is fixed since we want an increasing sequence. This makes the problem quite different. – Henry Oct 14 '17 at 04:57
  • @Henry True that, it's a DAG and can be solved in linear time using topological sorting. Maybe I should not attempt to solve math problems waaay past bed time :D – Gergely Kőrössy Oct 14 '17 at 05:09

2 Answers2

2

I assume we are looking for a strictly increasing sequence (this is not clear from the original problem description). This problem can then be solved by a dynamic programming approach:

1) sort the cells by their value into decreasing order.

2) in decreasing order assign the length of the longest path starting at this cell:

2a) if you cannot reach any of the previously visited cells assign 1

2b) otherwise assign 1 + max(reachable previous cell)

When this is finished, the overall maximum is the length of the longest path. The path itself can also be found by remembering the max cell in step 2b).

In the example this gives:

                                            0,3 2,1
cell    98  97  89  75  57  56  47  45  41  36  36  35  26  25  17  13
length   1   1   1   2   2   3   4   2   5   6   6   7   7   7   8   7
Henry
  • 42,982
  • 7
  • 68
  • 84
  • Making it into a graph that will be a DAG due to the increasing order constraint and applying DFS / topological sorting to get the topological order is way faster, it's `O(|V|+|E|)` which is linear time (I think, but I'm like half asleep, so who knows). – Gergely Kőrössy Oct 14 '17 at 05:20
  • @GergelyKőrössy This is true, it would be faster but I think more complex to program. – Henry Oct 14 '17 at 05:33
  • Variety is the coolest thing in programming. (Also I think about DFS because the teacher hinted using stack which could be used in DFS.) – Gergely Kőrössy Oct 14 '17 at 05:36
  • 2
    Although the algorithm here is good, it is not a valid answer for the question. Assignment says *"solve the problem using a stack"*. To me, that sounds like code is expected to do brute-force path-walking to find longest sequence of increasing values, because that is the skill-level for the assignment. – Andreas Oct 14 '17 at 06:03
  • @Andreas DFS uses a stack, so the topological sorting is technically still usable :P But yeah, the expected program is probably a simple back-tracking one. – Gergely Kőrössy Oct 14 '17 at 06:12
0

As far as I understand, you try to implement a depth-first search to find the longest path of increasing order. If so, first of all it is better to mark numbers you visited somehow. A convenient solution is an array. As far as the numbers are marked, you can use it to check whether the particular number has already been counted in an increasing sequence. This is as a little hint for you.

If you are still confused about a depth-first search, I would recommend to read the Depth-First Search Wikipedia page to get a better understanding of what the algorithm is all about.

HTH, Evgeniy

Evgeny Mamaev
  • 1,237
  • 1
  • 14
  • 31