CareerCup

this is longest increasing sequence problem, time complexity is O(n^2).

Hi,
I have a few doubts regarding the problem.
1) Suppose our array is 123476345.Now there are three sorted sub array
1234 76 345 Here '5' can also come with first array.like 12345.

2) Suppose our array is 1234765.Now there are two sorted sub array
1234 765 now again '5' can come with 1234 also.
so what is the correct position of 5?

/*
  array - input array
  start - starting index of array
  end - ending index of array
  subStart - starting index of the longest subsequence
  subEnd - ending index of the longest subsequence
*/
void subseq(int* array, int start, int end, int* subStart, int *subEnd)
{
   int bestStart = start; /* current longest sequence's start index */
   int bestEnd = start; /* current longest sequence's end index */

   *subStart = start;
   *subEnd = start;

   while(1) {
     bestStart = start;
     /* continue as long as the elements are non-decreasing */
     while((start < end) && (array[start] <= array[start+1]))
     {
        start++;
     }
     bestEnd = start;

     /* did we find a subsequence longer than the current one? */
     if((bestEnd - bestStart) > (*subEnd - *subStart))
     {
         *subStart = bestStart;
         *subEnd = bestEnd;
     }
     start++;

     /* we are done if the current subsequence is longer than the remaining number of elements. */
     if((*subEnd-*subStart) >= (end-start))
       break;
   }
}

Complexity is linear.

Approach 1: (Time Complexity: O(n2), Space complexity: O(n))

1) Do a linear traversal and store the indices of the array where array[current] > array[next] in a new array
2) In the array of indices, Loop from first index and check if array[currentIndex] < array[currentIndex+2]
3) If yes, remove currentIndex+1 and currentLongest sub sequence is from left till nextIndex (after removing currentIndex+1)
4) Repeat the steps 2,3 till all combinations are covered (like a nested for loop)

CurrentLength is compared with maximumLength at the end of each inner loop and store the indexes to be removed if current > maximum

Eg:

Input array: 20 24 28 49 5 50 51 62 4 70

Array of indices where array[current] > array[next]: 3, 7

Iteration 1:
if array[3] < array[5] => 49 < 50 = yes
currentLength = current(0) + length ((3-0)+1)+((7-5)+1)=7 (subtracting each set of indices and adding one to it)

if array[7] < array[9] => 62 < 70 = yes
currentLength = current(7) + length ((array.length-9)+1)=8 (subtracting each set of indices and adding one to it)

Repeat such iterations starting from each element in the indices array.

Approach 2: (Time Complexity: O(n), Space Complexity: O(1))
Note: This approach works ONLY when the last element of the array is the largest element.

1) Start from the tail of the array and iterate till start
2) if array[left] > array[right], remove the current element from maximum subsequence

Eg:

Input array: 20 24 28 49 5 50 51 62 4 70

Indices where array[left] > array[right]: 8, 4

When we remove these indices, we get the largest possible sorted sub sequence.

There is a simple logic to solve this, follow the below steps

1) Start with the first number and insert in array A
2) keep moving as long as it is in increasing order
3) The moment an item is skipped, store the first skipped index and move on by skipping any drops and inserting only increasing values to array A as step2 only

Now if there is an item skipped, start another iteration with that skipped index value saving it to array B and keep moving as long as it is in increasing order by dropping lower values and adding sequence values to Array B.

Return larger of Array A or B