Longest increasing subsequence 2d

Question

I have n sorted arrays of m integers in fixed order. I need to find a longest increasing subsequence such that every element in the subsequence belongs into exactly one of the arrays. Can I do better than O(n²)?

Answer 1

In line with @svs, this isn't possible to achieve in less than O(m * n). However, in practice, you can reduce the average worst time by terminating iteration through an array once you know you can't possibly find a longer subsequence within it.

Trivial loop:

maxList = []
for arr in arrays:
    last = arr[0] - 1
    tempList = []
    for element in arr:
        if element > last:
            tempList.append(element)
            if len(tempList) > len(maxList):
                    maxList = tempList

        else:
            tempList = [element]
        last = element

return (maxList, iters)

With redundant loop iterations ignored:

maxList = []
for arr in arrays:
    if len(maxList) == len(arr):
        break

    last = arr[0] - 1
    tempList = []
    for (index, element) in enumerate(arr):
        if element > last:
            tempList.append(element)
            if len(tempList) > len(maxList):
                    maxList = tempList[:]
        else:
            tempList = [element]

        # if continuing looking down the array could not result in a longer
        # increasing sequence
        if (len(tempList) + (len(arr) - (index + 1)) <= len(maxList)):
            break

        last = element

return (maxList, iters)

Answer 2

Yes it can be done via Dynamic Programming and memoization...the complexity would be O(n Log(base2) n) alias O(nLogn). To prove it - I have taken a external static complexity variable (named complexity) and increment in each iteration of recursion to show case that complexity will be O(nLogn) -

package com.company.dynamicProgramming;

import java.util.HashMap;
import java.util.Map;

public class LongestIncreasingSequence {

    static int complexity = 0;    // <-- here it is init to 0

    public static void main(String ...args){


        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        int n = arr.length;

        Map<Integer, Integer> memo = new HashMap<>();

        lis(arr, n, memo);

        //Display Code Begins
        int x = 0;
        System.out.format("Longest Increasing Sub-Sequence with size %S is -> ",memo.get(n));
        for(Map.Entry e : memo.entrySet()){

            if((Integer)e.getValue() > x){
                System.out.print(arr[(Integer)e.getKey()-1] + " ");
                x++;
            }
        }
        System.out.format("%nAnd Time Complexity for Array size %S is just %S ", arr.length, complexity );
        System.out.format( "%nWhich is equivalent to O(n Log n) i.e. %SLog(base2)%S is %S",arr.length,arr.length, arr.length * Math.ceil(Math.log(arr.length)/Math.log(2)));
        //Display Code Ends

    }



    static int lis(int[] arr, int n, Map<Integer, Integer> memo){

        if(n==1){
            memo.put(1, 1);
            return 1;
        }

        int lisAti;
        int lisAtn = 1;

        for(int i = 1; i < n; i++){
            complexity++;                // <------ here it is incremented to cover iteration as well as recursion..

            if(memo.get(i)!=null){
                lisAti = memo.get(i);
            }else {
                lisAti = lis(arr, i, memo);
            }

            if(arr[i-1] < arr[n-1] && lisAti +1 > lisAtn){
                lisAtn = lisAti +1;
            }
        }

        memo.put(n, lisAtn);
        return lisAtn;

    }
}

you try to run it and see the value of time complexity (derived from variable complexity) -

Longest Increasing Sub-Sequence with size 6 is -> 10 22 33 50 60 80 
And Time Complexity for Array size 9 is just 36 
Which is equivalent to O(n Log n) i.e. 9Log(base2)9 is 36.0
Process finished with exit code 0

the crux is, In every recursion we do calculate what is the LIS at ith index and store in memo map. Further when we are at (i+1)th iteration - due to memo map availability we dont need to re-calculate (recurs) entire 0 to ith index and it reduce the complexity from exponential to nlogn level.