How to find the longest increasing subarray in an array in O(N) time complexity ?

Question

1<=N<=1000000

1<=A[i]<=1000000000

 

Example : {2,1,5,6,7,8}

Output : 5

Long Increasing Sub-Array is : {1,5,6,7,8}

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

3(Use format option while adding code so it looks rich)

Answer 1

#Time Complexity - O(N)

#Language - C#

APPROACH

STEP 1: - Create a temporary variable and assign the initial array value to it as it will be helpful to compare the next value in loop.

STEP 2:-  Use a loop and start with index 1 and check if the array index value is greater than temp varaible in a loop. If so, increment the count.Else make the count value to zero.

STEP 3: - Assign the index value to temp variable in the loop so that temp will consists of next value in an array.

STEP 4 :- At last, if count value is greater than result, assign the count to result variable. Print the result+1 value because it compares (n-1) indexes.

 

CODE

using System;

public class Test
{
    public static void Main()
    {
        int[] arr={2,1,5,6,7,8};
        int temp=arr[0],count=0,result=0;
        for(int i=1;i<arr.Length;i++)
        {
            if(arr[i]>temp)
              count++;
            else 
               count=0;
               
         temp=arr[i];     

         if(count>result)
            result=count;
        }
      Console.WriteLine(result+1);
    }
}

Output: 5

Input 2: {2,1,0,6,7,8)

output 2 : 4