Increasing Array

Task:

You are given an array containing $n$ integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.

A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.

Input

The first line contains an integer $n$: the size of the array.

After this there are $n$ integers $x_1,x_2,\ldots,x_n$: the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints

• $1 \le n \le 2 \cdot 10^5$
  
• $1 \le x_i \le 10^9$
  

Solutions:

The most noticeable thing is It is substring. That means we only count the current character if the previous one is the same one. And If both of them are same, the current length is advanced by one. Otherwise, it should be reset to one. Meanwhile, we also have a variable that hole the longest length we have seen so far.

 1n=int(input())
 2arr=[int(i) for i in input().strip().split()]
 3def repetitions(n,arr):
 4    res,last=0,arr[0]
 5    for i in range(1,len(arr)):
 6        if last>arr[i]:
 7            res+=(last-arr[i])
 8        else:
 9            last=arr[i]
10    return res
11print(repetitions(n,arr))
12 

Time complexity: O(N).

Space complexity: O(1).