Algorithm tricks 1

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 to 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

Advertisements