Longest subframe that has elements in ascending order?

Given an array = {1 2 3 3 2 4 6 7}

The longest incremental subaraquit is 2 4 6 7. Note that this is not the same as the longest incremental subsequence, since the values ​​must be contiguous.

Is there any O (n) solution for this task?

+3


source to share


10 replies


You can just use dynamic programming.

Pseudocode:



def DP(a[]):
    dp[1] = 1
    for i = 2 to n:
        if a[i] > a[i - 1]:
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = 1

      

+13


source


, o (n). , . . , . , reset . .



+4




  1 < 2 < 3 >= 3 >= 2 < 4 < 6 < 7
| 1   2   3  | 1  | 1   2   3   4 <- Length of runs

      

Move the array from left to right. Keep track of how long the current run is.

When the run ends, compare it to the best run so far, for which you store the length and position where it ended. If a startup that just ended is better, update with the best data.

  1 < 2 < 3 >= 3 >= 2 < 4 < 6 < 7
| 1   2   3  | 1  | 1   2
          ^
          Longest run, 
          ending at index 2

  1 < 2 < 3 >= 3 >= 2 < 4 < 6 < 7
| 1   2   3  | 1  | 1   2   3   4
          ^                     ^
          Longest run,          Current run ends
          ending at index 2     Better than last longest run, update

      

Since you are traversing the array only once at a time, accessing one element at a time, and in addition to the best data, you are doing constant time for each element. Hence the algorithm works in O(n)

.

+3


source


You have to solve it in linear time as follows. Maintain at every point

  • The length / starting point of the longest enlarging subarar visible so far is
  • The last item in the array that you saw (or a checkpoint if you haven't seen anything yet), and
  • Length of longest incremental subaram ending with current value.

Then you can iterate over the array in one pass and do the following for each value:

  • If the previous value is sentinel:
    • Set the previous value to the current value.
    • Set the current length to 1.
  • Otherwise, if the previous value is less than the current value:
    • Set the previous value to the current value.
    • Increase the length of the current submachine.
  • Otherwise, if the previous value is greater than the current value:
    • Set the previous value to the current value
    • Set the current length to 1.
  • Regardless of the above, if the current length is greater than the maximum length found:
    • Set the maximum length found for the current length.
    • Write down the beginning of the sequence you've found so far (this is the current length minus the position of the first element in that sequence).

This means O (1) runs O (n) times, so the overall solution runs in O (n) time.

Hope this helps!

+2


source


    int flag = 0;
    int maxSubarray =0;
    int maxStart=0,maxEnd=0,start=0,end=0;
    for(int i=1;i<n;i++){
        if(a[i-1]<a[i]){
            if(flag!=1){
                start = i-1;
                flag=1;
            }
            if(i == n-1){
                end = n-1;
            }
        }
        else{
            if(flag==1 ){
                end = i-1;
                flag =0;
            }
        }
        if(maxSubarray < end - start){
            maxSubarray = end - start;
            maxStart = start;
            maxEnd = end;
        }
    }

    System.out.println(maxSubarray);
    System.out.println("Starting index = "+maxStart+" Ending index = "+maxEnd);` 

      

`

Time complexity : O (n) Space complexity : O (1)

+2


source


Jun HU's answer is correct, but I don't think we need to maintain an array that takes O (n) space. We can instead keep track of the size of the current subarray, something like

 int maxSize, currentSize = 1;
 for (int i = 1; i < array.size(); i++) {
     if (array[i] > array[i-1]) {
         currentSize++;
         maxSize = max(currentSize, maxSize);
     } else {
         currentSize = 1; 
     }
 }

      

This works because, since the array is sorted, if the current item is not higher than the previous one, the current submachine is no longer in ascending order and therefore we no longer care about its size. Thus, we achieve constant space complexity while maintaining linear time complexity.

+1


source


def lis(a):                                                                                                                                                   
    m = 0                                                                                                                                                     
    c = 1                                                                                                                                                     
    index = 0                                                                                                                                                 

    for i in xrange(1, len(a)):                                                                                                                               
        x = a[i]                                                                                                                                              
        if x > a[i - 1]:                                                                                                                                      
            c += 1                                                                                                                                            
        else:                                                                                                                                                 
            if c > m:                                                                                                                                         
                m = c                                                                                                                                         
                index = i                                                                                                                                     
                c = 1                                                                                                                                         
    if c > m:                                                                                                                                                 
        m = c                                                                                                                                                 
        index = i                                                                                                                                             
    return a[i - m + 1: i + 1] 

      

0


source


Java's O (n) implementation, also generic, can be used for anything!

import java.util.Arrays;

public class LongestIncreasing {

    private static class PairHolder<T> {
        int start = -1;
        int end = -1;
        int weight = -1;
        PairHolder(int start, int end) {
            this.start = start;
            this.end = end;
            this.weight = start == -1 ? -1 : end-start+1;
        }

        String getSubArray(T[] arr) {
            return Arrays.toString(Arrays.copyOfRange(arr, start, end+1));
        }

        @Override
        public String toString() {
            return "[" + start + ", " + end + ", weight: " + weight + "]";
        }
    }

    public static <T extends Comparable<? super T>> void getContiguousChain(T[] chain) {
        int start = -1, end = -1;
        PairHolder<T> longest = new PairHolder<T>(-1, -1);
        for (int i = 0; i < chain.length - 1; i++) {
            if (start == -1) {
                start = i;
                end = i;
            }

            if (chain[i+1].compareTo(chain[i]) == -1 || chain[i+1].compareTo(chain[i]) == 0) {
                if (end-start+1 > longest.weight) {
                    longest = new PairHolder<T>(start, end);
                }

                start = -1; end = -1;
                continue;
            }

            end = i+1;
        }

        if (end-start+1 > longest.weight) { //corner case where last element of chain is also end of array
            longest = new PairHolder<T>(start, end);
        }

        System.out.println(longest.getSubArray(chain));
    }

    public static void main(String[] args) {
        Integer[] arr = {2, 3, 3, 4, 5, 6, 2, 9, 10, 12, 14, 13};
        getContiguousChain(arr);
    }

}

      

0


source


This will give you a range (start and end index).

public static Range getLargest(int[] array) {
    int max = 1;
    int start = 0;
    int aux = 0;
    int count = 1;
    for (int i = 1; i < array.length; i++) {
        if (array[i] > array[i - 1]) {
            count++;
        } else {
            aux = i;
            count = 1;
        }
        if (count > max) {
            max = count;
            start = aux;
        }
    }
    return new Range(start, start + max - 1);
}

public static class Range {
    public final int start;
    public final int end;
    public Range(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

      

0


source


This is not a dynamic programming solution, but I just tried it for some scenarios and it looks good with that. May be a good starting point for you.

public static int MaxSlice(int[] A)
    {
        //100,40,45,50,55,60, 30,20,40,25,28,30
        int maxstartIndex = 0;
        int MaxAscendingCount = 0;
        int thisStartIndex = 0;
        int thisAscendingCount = 0;
        bool reset = false;
        bool wasLastAscending = false;
        for (int i = 0; i < A.Length-1; i++ )
        {
            if (A[i + 1] > A[i])
            {
                if(!wasLastAscending)
                    thisStartIndex = i;
                thisAscendingCount++;
                wasLastAscending = true;
            }
            else
            {
                reset = true;
                wasLastAscending = false;
            }

            if (reset && thisAscendingCount > MaxAscendingCount)
            {
                MaxAscendingCount = thisAscendingCount;
                maxstartIndex = thisStartIndex;
                reset = false;
                thisAscendingCount = 0;

            }

        }
        MaxAscendingCount = thisAscendingCount;
        maxstartIndex = thisStartIndex;
        return maxstartIndex;
    }

      

0


source







All Articles