# Trick 1

Considering the following code (*)

int len = 1; for(int i = 1; i <= n; i++) { num[a[i]-1] = 0; num[a[i]]++; num[a[i]+1] = 0; len = max(len, num[a[i]]); } cout << len;

“len” variable computed in this case is the **length of the longest consecutive subsequence** of array a that **contains same values**

The same approach is applied when we want to find out the length of the longest consecutive subsequence SUB, so that max(SUB) – min(SUB) <= K, by assuming all the values between x and x-K have the same property.

**In(*) we: **

set *num[a[i]]++;*

upper bound and lower bound: *num[a[i]-1] = num[a[i]+1] = 0*

query result: *len = max(len, num[a[i]]);*

**Similarly we have:**

*num[a[i]]++, num[a[i]-1]++, num[a[i]-K]++… *

upper bound and lower bound: num[a[i]+1] = num[a[i]-K-1] = 0

query result: len = max(len, num[a[i]], … , num[a[i]-K])

# Trick 2

At each specific position i of an 1-dimension array, we can use dynamic programming to query** the number of elements that have arbitrary value to the left** and t**o the right** of the array, with complexity *O(nlogn) *using map:

map<int, int> l, r; for(int i = 1; i <= n; i++) r[a[i]]++; for(int i = 1; <= n; i++) { r[a[i]]--; // eliminate current element // TO-DO // now r[x] is the number of elements: a[0..i-1] = x // and l[x] is the number of elements: a[i+1..n] = x l[a[i]]++; // end of loop, i becomes left index }

Happy coding