CareerCup

it's very similar to merge sort, we have to maintain another array with the same size that keeps the current "qaz" of each number, assume the initial array is 33 , 48 , 26 , 58 , 41 , 59
I just explain the last step of the merge sort
First half: 26(0), 33(1), 48(0)
Second half: 41(1), 58(1), 59(0)
Update "qaz" of the first half before merging the two sorted arrays,
-traverse both arrays from end to the beginning,
-move the pointer which is pointing to the bigger number,
-when moving the pointer of the second array, increase added_qaz
-when moving the pointer to the first array, apply (add) qaz before moving
-when the loop ends, increase qaz of the numbers in the first half from where the pointer is to the beginning
void UpdateQAZ(int low, int mid, int high)
{
int i,j;

added_qaz = 0;

i = mid;
j = high;

while ( ( i >= 0 ) && ( j > mid ) )
{
if ( A[ j ] > A[ i ] )
{
added_qaz++;
j--;
}
else
{
A[ i ].qaz += added_qaz;
i--;
}
}

if ( j <= mid )
{
for ( x = i ; x >=low ; x-- )
{
A[ x ].qaz += added_qaz;
}
}
}
Trace:
low = 0, mid = 2, high=5, added_qaz = 0
iterations:
1. i = 2, j = 5, added_qaz = 1
2. i = 2, j = 4, added_qaz = 2
3. i = 2, j = 3, added_qaz = 2, increase qaz of 48 by 2
4. i = 1, j = 3, added_qaz = 3
5. i = 1, j =2 : loop ends
Second loop:
x = 1 => , increase qaz of 33 by 3
x = 0 => , increase qaz of 26 by 3

Modified the MergeSort algorithm for this problem - Time Complexity - O(nlogn)

#include<utility>
#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

unordered_map<int, int> q;

unordered_map<int, int> initializeQAZ(vector<int> &A, int vsize)
{
    unordered_map<int, int> qaz;
    for(int i = 0; i < vsize; i++)
    {
        qaz[A[i]] = 0;
    }
    return qaz;
}

vector<int> merge_sort(vector<int> &l, vector<int> &r)
{
    vector<int> result;
    unsigned left_it = 0, right_it = 0;
    while(left_it < l.size() && right_it < r.size())
    {
        if(l[left_it] < r[right_it])
        {
            result.push_back(l[left_it]);
            q[l[left_it]] += (r.size() - right_it);
            left_it++;
        }
        else
        {
            result.push_back(r[right_it]);
            right_it++;
        }
    }
    while(left_it < l.size())
    {
        result.push_back(l[left_it]);
        left_it++;
    }
    while(right_it < r.size())
    {
        result.push_back(r[right_it]);
        right_it++;
    }
    return result;
}

vector<int> mergeSort(vector<int> &A)
{
    if(A.size() == 1)
        return A;

    vector<int>::iterator middle = A.begin() + A.size()/2;
    vector<int> leftV(A.begin(), middle);
    vector<int> rightV(middle, A.end());

    leftV = mergeSort(leftV);
    rightV = mergeSort(rightV);

    return merge_sort(leftV, rightV);
}

int main(int argc, char** argv)
{
    int B[] = {33, 25, 26, 58, 41, 59};
    vector<int> A(B, B + sizeof(B) / sizeof(B[0]));
    q = initializeQAZ(A, A.size());
    vector<int> sortedA = mergeSort(A);
    for(int i = 0; i < A.size(); i++)
    {
        cout << A[i] << "  ";
    }
    cout << endl;
    for(int i = 0; i < sortedA.size(); i++)
    {
        cout << sortedA[i] << "  ";
    }

    cout << endl;
    for(int i = 0; i < A.size(); i++)
    {
        cout << A[i] << "  " << q[A[i]] << endl;
    }
    return 0;
}

This is another MergeSort-like solution in Java, that just tries to be easier to read.
It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

public class QAZ {

	public static void main(String[] args) {
		int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
		System.out.println(getMaxQAZ(array));
	}

	public static int getMaxQAZ(int[] array){
		if (array == null) {
			return 0;
		}
		return getMaxQAZ(array, 0, array.length).qaz;
	}
		
	private static QAZResult getMaxQAZ(int[] array, int start, int end) {
		
		if (end - start <= 3) {
			return getLastLocalMaxQAZ(array, start, end);
		}
		
		int middle = (end + start) / 2;
		
		QAZResult leftResult = getMaxQAZ(array, start, middle);

		QAZResult rightResult = getMaxQAZ(array, middle, end);
		
		if (leftResult.minVal < rightResult.minVal) {
			return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
		}
		
		for (int i = middle; i < end; i++) {
			if (leftResult.minVal < array[i]) {
				leftResult.qaz++;
			}
		}
		
		return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
		
		
	}
	
	private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){
		
		int minVal = array[start];
		int qaz = 0;
		for (int i = start + 1; i < end; i++) {
			if (array[i -1] < array[i]) {
				qaz++;
			} else {
				minVal = array[i];
			}
		}
		return new QAZResult(minVal, qaz);
	}
}

class QAZResult {
	int minVal;
	int qaz;
	
	public QAZResult(int minVal, int qaz) {
		this.minVal = minVal;
		this.qaz = qaz;
	}
}

modified merge sort is nice solution.

I do have 1 more algo which is having complexity : O(nlogn).

say array is
A [] = { 33 , 25 , 26 , 58 , 41 , 59}

step 1 : create ArrayList of size = A.length
step 2 : sort ArrayList in ascending order O(nlog(n))

ArrayList => { 25 , 26 , 33, 41, 58 , 59 }

step 3 : choose 1st element of A[] ie 33
=> qaz(33) => total elements in ArrayList after 33
=> qaz(33) = 3

remove element 33 from ArrayList
now ArrayList = {25 , 26 , 41, 58 , 59 }

step 4: choose next element from A[] ie 25
=> qaz(25) = total elements in ArrayList after 25
=> qaz(25) = 4

remove element 25 from ArrayList
now ArrayList = {26 , 41, 58 , 59 }

step 5: choose next element from A[] ie 26
=> qaz(26) = total elements in ArrayList after 26
=> qaz(26) = 3

remove element 26 from ArrayList
now ArrayList = {41, 58 , 59 }

step 6: choose next element from A[] ie 58
=> qaz(58) = total elements in ArrayList after 58
=> qaz(58) = 1

remove element 58 from ArrayList
now ArrayList = {41 , 59 }

step 7: choose next element from A[] ie 41
=> qaz(41) = total elements in ArrayList after 41
=> qaz(41) = 1

remove element 41 from ArrayList
now ArrayList = { 59 }

last step: choose next element from A[] ie 59
=> qaz(59) = total elements in ArrayList after 59
=> qaz(59) = 0

remove element 59 from ArrayList
now ArrayList = {}

This is another MergeSort-like solution in Java, that just tries to be easier to read.
It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

public class QAZ {

	public static void main(String[] args) {
		int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
		System.out.println(getMaxQAZ(array));
	}

	public static int getMaxQAZ(int[] array){
		if (array == null) {
			return 0;
		}
		return getMaxQAZ(array, 0, array.length).qaz;
	}
		
	private static QAZResult getMaxQAZ(int[] array, int start, int end) {
		
		if (end - start <= 3) {
			return getLastLocalMaxQAZ(array, start, end);
		}
		
		int middle = (end + start) / 2;
		
		QAZResult leftResult = getMaxQAZ(array, start, middle);

		QAZResult rightResult = getMaxQAZ(array, middle, end);
		
		if (leftResult.minVal < rightResult.minVal) {
			return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
		}
		
		for (int i = middle; i < end; i++) {
			if (leftResult.minVal < array[i]) {
				leftResult.qaz++;
			}
		}
		
		return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
		
		
	}
	
	private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){
		
		int minVal = array[start];
		int qaz = 0;
		for (int i = start + 1; i < end; i++) {
			if (array[i -1] < array[i]) {
				qaz++;
			} else {
				minVal = array[i];
			}
		}
		return new QAZResult(minVal, qaz);
	}
}

class QAZResult {
	int minVal;
	int qaz;
	
	public QAZResult(int minVal, int qaz) {
		this.minVal = minVal;
		this.qaz = qaz;
	}
}

MAXIMUM-QUAZ ( int[] array )

1. MaxQaz = 0

2. Q = PRIORITY-QUEUE

3. for i = array.length - 1 to 0

4.     index = Q.insert ( array [ i ] )   // return index of newly inserted element

5.     qaz = Q.size - index

6.     if ( qaz > MaxQaz )

7.         MazQaz = qaz

8. return MazQaz

Since they want O(nlogn) they probably want something to do with sorting or divide and conquer. My solution is merge sort, but you have another array storing counts :
Lets call the original array A, and the max array Max
1. Recursively cut the array in half like in merge sort
2. Merge Process:
Let's assume leftIndex is the starting index of the left side and rightIndex is the starting of the right side. Lets say endRight is the end of the right and endLeft is end of left.
1. Check to see whether the starting index of the right side or left side is bigger.
2. If the left side is bigger, update Max[leftIndex] += endLeft - rightIndex. Then do the swapping in the same way you would for both arrays.
3. If the right side is bigger, just do the swapping for both array like you would normally.

Once you are done you can just search for the biggest number in Max[], which would take O(n). So the complexity is nLgn + n, or O(nLgn).

I wonder if there is a way to do this without an extra array. You can probably keep track of the max during the merge process so you can cut out the last O(n) operation. Let me know if I made any mistakes!

Not enough time to complete the code, but this is the basic idea. We modify merge sort, so that whenever we add in an element from "the left side", we will add the difference between the end of the right side and the right side iterator to a hashed stored value for the element's qez.

For example, if we merge:

[11, 10, 5, 12, 20]

Our steps look like this:

[11, 10] -> [10, 11], No QEZ
[5, 12] -> QEZ of 5 is 1
[5, 12], [20] -> QEZ of 5 increases by 1, QEZ of 12 becomes 1

now when we merge

[10, 11] and [5, 12, 20]

[5] -> no QEZ change
[5,10] -> QEZ of 10 is now 2 because right pointer is pointing at 12
[5, 10, 11] -> QEZ of 11 is 2 because right pointer is pointing at 12
[5, 10, 11, 12, 20] -> No QEZ change for 12 and 20 since while loop ends the merge

Not enough time to complete the code, but the basic gist of the merge method is like this:
end refers to the location of the end of right pointer so in the case of [10, 11] and [5, 12, 20], right would be = to 2 and end would be equal to 2 + 2 = 4.
Sorry, again for incompleteness

merge(int[] arr, int[] new, int l, int r, int end, HashMap hm) {
  
  boolean done = false;
  int i = l;
  int j = r;
  int k = l;
  while(!done) {

    if (arr[left] >= arr[right]) {

      new[k++] = arr[j++];
      //handle ending case of merge here
    }

    else {

      new[k++] = arr[j++];
      hm.put(arr[k], hm.get(arr[k] + (end - j)) );
    }
  }

}

This can be helpful:
a recursive function which returns a TreeMap<Integer,Integer> where it contains the number and the qaz of this number.
this function divide each time the array into 2 sub-arrays and then merge them, iterate the left tree map and for each number , do a binary search to find the first larger number than this number the add to the value of this number -> rightTreeMap.size()-1-(the index of the number) and so on.

I think this is just O(n). Keep 2 pairs. One has smallest number and one has max qaz. Update them while traversing the array. Am I missing something?

#include <stdio.h>

struct Pair
{
	int v;
	int qaz;
	Pair(int _v = 0, int _qaz = 0): v(_v), qaz(_qaz){}
};

void findMaxQaz(int v[], int len)
{
	Pair smallest(v[0], 0);
	Pair maxQaz(v[0], 0);
	
	for (int i = 1; i < len; ++i)
	{
		if (v[i] > smallest.v)
		{
			smallest.qaz++;
		}
		else
		{
			smallest.qaz = 0;
			smallest.v = v[i];
		}
		if (v[i] > maxQaz.v)
		{
			maxQaz.qaz++;
		}
		if (smallest.qaz > maxQaz.qaz)
		{
			maxQaz.v = smallest.v;
			maxQaz.qaz = smallest.qaz;
		}
	}
	printf("%d qaz:%d", maxQaz.v, maxQaz.qaz);
}

int main()
{
	//int v[] = {2, 3, 1, 4, 5};
	int v[] = {33 , 25 , 26 , 1 , 5 ,6 ,7 ,9 , 14 ,20,21,23,29};
	findMaxQaz(v, sizeof(v)/sizeof(int));
	return 0;
}

Walk the array in reverse, inserting values into a min-oriented heap as you go. The 'qaz' for each number is the number of elements beneath it in the heap when you insert it. Keep track of the max qaz after each insertion. This will be an O(n log n) algorithm.

how about this:
sort the array, scan the sorted array, for each item i, let ans = max(ans, size - i - ori_i) where ori_i is the original index of the item.

This is another MergeSort-like solution in Java, that just tries to be easier to read.
It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

public class QAZ {

	public static void main(String[] args) {
		int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
		System.out.println(getMaxQAZ(array));
	}

	public static int getMaxQAZ(int[] array){
		if (array == null) {
			return 0;
		}
		return getMaxQAZ(array, 0, array.length).qaz;
	}
		
	private static QAZResult getMaxQAZ(int[] array, int start, int end) {
		
		if (end - start <= 3) {
			return getLastLocalMaxQAZ(array, start, end);
		}
		
		int middle = (end + start) / 2;
		
		QAZResult leftResult = getMaxQAZ(array, start, middle);

		QAZResult rightResult = getMaxQAZ(array, middle, end);
		
		if (leftResult.minVal < rightResult.minVal) {
			return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
		}
		
		for (int i = middle; i < end; i++) {
			if (leftResult.minVal < array[i]) {
				leftResult.qaz++;
			}
		}
		
		return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
		
		
	}
	
	private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){
		
		int minVal = array[start];
		int qaz = 0;
		for (int i = start + 1; i < end; i++) {
			if (array[i -1] < array[i]) {
				qaz++;
			} else {
				minVal = array[i];
			}
		}
		return new QAZResult(minVal, qaz);
	}
}

class QAZResult {
	int minVal;
	int qaz;
	
	public QAZResult(int minVal, int qaz) {
		this.minVal = minVal;
		this.qaz = qaz;
	}
}

This is another MergeSort-like solution in Java, that just tries to be easier to read.
It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

public class QAZ {

	public static void main(String[] args) {
		int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
		System.out.println(getMaxQAZ(array));
	}

	public static int getMaxQAZ(int[] array){
		if (array == null) {
			return 0;
		}
		return getMaxQAZ(array, 0, array.length).qaz;
	}
		
	private static QAZResult getMaxQAZ(int[] array, int start, int end) {
		
		if (end - start <= 3) {
			return getLastLocalMaxQAZ(array, start, end);
		}
		
		int middle = (end + start) / 2;
		
		QAZResult leftResult = getMaxQAZ(array, start, middle);

		QAZResult rightResult = getMaxQAZ(array, middle, end);
		
		if (leftResult.minVal < rightResult.minVal) {
			return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
		}
		
		for (int i = middle; i < end; i++) {
			if (leftResult.minVal < array[i]) {
				leftResult.qaz++;
			}
		}
		
		return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
		
		
	}
	
	private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){
		
		int minVal = array[start];
		int qaz = 0;
		for (int i = start + 1; i < end; i++) {
			if (array[i -1] < array[i]) {
				qaz++;
			} else {
				minVal = array[i];
			}
		}
		return new QAZResult(minVal, qaz);
	}
}

class QAZResult {
	int minVal;
	int qaz;
	
	public QAZResult(int minVal, int qaz) {
		this.minVal = minVal;
		this.qaz = qaz;
	}
}

struct qaz_pair
{
	int value;
	size_t index;
};

bool operator < (const qaz_pair& lhs, const qaz_pair& rhs)
{
	return lhs.value < rhs.value;
}

int qaz(const vector<int>& numbers, int number)
{
	// O(n)
	vector<qaz_pair> tmp;
	for (const auto n : numbers )
		tmp.push_back( qaz_pair{ n, tmp.size() } );

	// O(nlogn)
	sort(tmp.begin(), tmp.end());

	qaz_pair number_pair;
	number_pair.value = number;

	auto found = lower_bound(tmp.begin(), tmp.end(), number_pair);
	if (tmp.end() == found || found->value != number)
		return -1;

	// O(n)
	int result = 0; 
	int previous = found->value;
	const size_t index = found->index;
	for (; tmp.end() != found ; previous = found->value, ++found )
	{
		if (found->index > index)
			if (previous != found->value)
				result++;
	}

	return result;
}

void Google6()
{
	const vector<int> numbers { 33 , 25 , 26, 26 , 58 , 41, 41 , 59, 59 };

	assert( -1 == qaz(numbers, 0) );
	assert( -1 == qaz(numbers, 100) );

	assert( 3 == qaz(numbers, 33) );
	assert( 4 == qaz(numbers, 25) );
	assert( 3 == qaz(numbers, 26) );
	assert( 1 == qaz(numbers, 58) );
	assert( 1 == qaz(numbers, 41) );
	assert( 0 == qaz(numbers, 59) );
}

Here's the short code for the heap-reverse-filling approach in Java.

public int maxQaz(int[] arr) {
    int max = 0;
    TreeSet<Integer> heap = new TreeSet<>();
    for (int i = arr.length-1; i >= 0; i--) {
        heap.add(arr[i]);
        max = Math.max(max, heap.tailSet(arr[i], false).size());
    }
    return max;
}

If we know for an array (having N elements) index i (0<=i<N), the number of elements which are smaller than array[i], say X, then the QAZ value of array[i] = (N-i-1)-X.
The number of elements smaller than array[i], say X, will introduce X array inversions to the right of index i. So we can just count the number of inversions at index i and calculate the QAZ value keeping track of the maximum. Since this is reduced to counting inversions we can of course use a modified merge sort algorithm but I suggest using a Fenwick tree which is much simpler to code. Complexity: O(nlogn).
Here's the code to elaborate:

public void solve(int[] A){
	int N = A.length;
	int[] bit = new int[N+1];
	int[] rank = Arrays.copyOf(A, N);
	Arrays.sort(rank);
	for (int i = 0; i < A.length; i++) {
		int idx = Arrays.binarySearch(rank, A[i]);
		A[i] = idx+1;
	}
	int maxQAZ = Integer.MIN_VALUE;
	for(int i=N-1;i>=0;i--)
	{
		int qaz = (N-i-1) - read(bit, A[i]-1);
		maxQAZ = Math.max(maxQAZ, qaz);
		update(bit, A[i],1,N);
	}
	System.out.println(maxQAZ);
}
private int read(int[] bit, int idx){
	int sum=0;
        while (idx>0)
        {
              	sum += bit[idx];
              	idx -= (idx & -idx);
        }
        return sum;
}
private void update(int[] bit, int idx, int val, int max){
	while (idx <= max)
        {
              bit[idx] += val;
              idx += (idx & -idx);
        }
}

Shorter algo based on the observation that the qaz(#i) = max(0, order of #i in the sorted array - #i).

int maxQaz(const vector<int> &v) {
	vector<pair<int, int> > pv;
	int n = v.size();
	for (int i = 0; i < n; i++) {
		pv.push_back(make_pair(v[i], i));
	}
	stable_sort(pv.begin(), pv.end());
	reverse(pv.begin(), pv.end());
	int ret = 0;	// when input is empty, result is 0.
	for (int i = 0; i < n; i++) {
		ret = max(ret, i - pv[i].second);
	}
	return ret;
}

As many people discussed, a O(nlogn) solution can be achieved by merge sort. Please check my analysis and solution: allenlipeng47.com/PersonalPage/index/view/126/nkey

package feb;

public class QAZ {

	public static void main(String[] args) {
		int[] arr = { 7, 8, 2, 3, 4, 5 };
		int qaz = qaz(arr);
		System.out.println(qaz);
	}

	public static int qaz(int[] arr) {
		int[] eleTimes = new int[arr.length];
		int[] helperQaz = new int[arr.length];
		int[] helperTimes = new int[arr.length];
		return qazUtil(arr, eleTimes, 0, arr.length - 1, helperQaz, helperTimes);
	}

	public static int qazUtil(int[] arr, int[] eleTimes, int start, int end,
			int[] helperQaz, int[] helperTimes) {
		if (start > end) {
			return 0;
		}
		if (start == end) {
			return 0;
		}
		int mid = start + (end - start) / 2;
		int qazLeft = qazUtil(arr, eleTimes, start, mid, helperQaz, helperTimes);
		int qazRight = qazUtil(arr, eleTimes, mid + 1, end, helperQaz,
				helperTimes);
		// 1. Update eleTimes in left part.
		int pointerL = mid, pointerR = end;
		int added = 0;
		while (pointerL >= start) {
			while (arr[pointerL] < arr[pointerR] && pointerR >= mid + 1) {
				pointerR--;
				added++;
			}
			eleTimes[pointerL] += added;
			qazLeft = (eleTimes[pointerL] > qazLeft) ? eleTimes[pointerL]
					: qazLeft;
			pointerL--;
		}
		// 2. Mergesort left and right part into helperQaz, helperTimes
		pointerL = start;
		pointerR = mid + 1;
		int helpIndex = start;
		while (pointerL <= mid && pointerR <= end) {
			if (arr[pointerL] < arr[pointerR]) {
				helperQaz[helpIndex] = arr[pointerL];
				helperTimes[helpIndex] = eleTimes[pointerL];
				pointerL++;
			} else {
				helperQaz[helpIndex] = arr[pointerR];
				helperTimes[helpIndex] = eleTimes[pointerR];
				pointerR++;
			}
			helpIndex++;
		}
		while (pointerL <= mid) {
			helperQaz[helpIndex] = arr[pointerL];
			helperTimes[helpIndex] = eleTimes[pointerL];
			pointerL++;
			helpIndex++;
		}
		while (pointerR <= end) {
			helperQaz[helpIndex] = arr[pointerR];
			helperTimes[helpIndex] = eleTimes[pointerR];
			pointerR++;
			helpIndex++;
		}
		// 2.2 Copy result from helperQaz, helperTimes back to arr, eleTimes
		for (int i = start; i <= end; i++) {
			arr[i] = helperQaz[i];
			eleTimes[i] = helperTimes[i];
		}
		return Math.max(qazLeft, qazRight);
	}

}

How about ~20 LOC in java:

import java.util.*;

public class QAZ {
    static int findMaxQaz(List<Integer> list) {
        TreeSet<Integer> set = new TreeSet<>();
        int maxQaz = -1, maxVal = -1;
        Collections.reverse(list);
        for (int i : list) {
            set.add(i);
            int qaz = set.tailSet(i).size();
            if (maxQaz < qaz) {
                maxVal = i;
                maxQaz = qaz;
            }
        }
        return maxVal;
    }
    
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(88, 77, 6, 5, 4, 3);
        System.out.println(findMaxQaz(list));
    }
}

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

alternate solution (not using merge sort):

Step1:
Make a second list and sort that list but keep track of where each element in the sorted list is stored within the original list.
[n log n, for the sorted list you can use a class that has a number as one class variables and "position in original list" as a second class variable]

Step 2:
Starting at the first element of the sorted list, for each element i, take

min ((n-1)-sortedListPosition, (n-1)-originalListPosition)

This is the myMaxPossibleQaz (weird name to make writing later easier),
the first item is the number of elements greater than the current element in the list as a whole,
the second item is the qaz assuming that all elements after the position of the current element in the original list are greater than the current element if all elements after element i within the original list are greater

The min of these is the highest possible qaz (given the set and the position of the current element in the original set). The highest possible qaz is lowered every time a smaller element is in front of i).

Make a list of these myMaxPossibleQaz values (or add another class variable to the objects within the sorted list) [n time].

Step 3.0

Going through each element i in the sorted list and keep track of the farthest left original position so far (this is because, any future elements in the sorted list that have an original position greater than this will definitely have a greater qaz, so we can ignore them. They will have a greater qaz because, in the original list, they appear after at least one number that they are greater than, so whatever their qaz is, the earlier number will have at least their qaz + 1)

Step 3.5
If future elements within the sorted list have an earlier position within the original list than we have seen so far then their qaz is

myMaxPossibleQaz - mySortedListPosition

This is because maxPossibleQaz is reduced by having numbers that are smaller than you appear after you in the original list, and every element so far has been smaller than the current element and after the current element in the original list.

So when iterating through the sorted list if the elements are to the right of the leftmost original position seen so far, we move on, if they are to the left, we update the leftmost seen position and calculate the qaz using the (myPossibleQaz - mySortedListPosition) formula.

{{
std::pair<int,int> qaz(int* A, int len)
{
std::vector<std::pair<int,int>> VA;
for(int i = 0; i < len; ++i)
VA.push_back(std::make_pair(A[i], i));

std::sort(VA.begin(), VA.end()); O(n log n)

std::pair<int,int> B = std::make_pair(-1,-1);
for(int i = len-1; i >= 0; --i) //O(n)
{
int v = std::min(len-(VA[i].second+1), len-(i+1));
if(v > B.second)
{
B = VA[i];
B.second = v;
}
}
return B;
}
}}

I would think that replacing std::sort with a radix sort would even give a O(n) solution.

Iterate from end to start, in each iteration insert the current element to a binary tree. Before each insertion count how many numbers are greater than this element and that's the qaz of the current element. Dynamically update the max qaz each time.

Iterate from end to start, in each iteration insert the current element to a binary tree. Before each insertion count how many numbers are greater than this element and that's the qaz of the current element. Dynamically update the max qaz each time.

Iterate from end to start, in each iteration insert the current element to a binary tree. Before each insertion count how many numbers are greater than this element and that's the qaz of the current element. Dynamically update the max qaz each time.

qaz problem is just longest incrementing subsequence in diguise.
There is a solution to this problem in O(nlogn).

# n squared qaz solution
def qaz(data):

    n = len(data)

    max_counter = 0

    elements = []

    for i in range(0,n):

        candidate_counter = 0

        for j in range(i + 1,n):

            if data[j] > data[i]:

                candidate_counter += 1

        if candidate_counter > max_counter:

            max_counter = candidate_counter

            del elements[:]

            elements.append(data[i])

        elif candidate_counter == max_counter:

            elements.append(data[i])

    return max_counter, elements[0]









##### This is nlogn solution in case you replace the data structure which holds the local minimums with an AVL tree.
##### I did not use an AVL tree since it is easier to understand the solution this way.
##### in the worst case we are doing a binary search ~n times to find max over all candidates which is smaller then new value in case it is bigger the min over all minimums.
##### so nlogn in the worst case. This is not optimal since deleting from an array may result linear time while deleting from AVL will result logarithmic time.
##### a tester which validates against the trivial solution runs.
##### By the way it took a day to think about and implement.could not have done it in an interview.

class QAZcandidate(object):

    def __init__(self, value):

        self.value = value

        self.rankUP = 0

        self.rankDOWN = 0


def find_max_smaller_minimum(data,key, index=0):

    if len(data) == 0:

        return data[0], index

    middle = len(data)/2

    element = data[middle]

    if element.value > key:

        return find_max_smaller_minimum(data[middle:],key,index + middle)

    else:

        #element.value < key
        if middle > 0:

            if data[middle - 1].value < key:

                return find_max_smaller_minimum(data[0:middle],key,index)

            else:
                #we found max smaller minimum
                return data[middle], middle + index

        #element.value < key and its the largest minimum
        else:

            return data[middle], middle + index


def qaz_hard(data):

    if len(data) <= 1:

        return

    local_minimals = []

    local_minimals_last_minimal_index = 0

    array_minimal_index = 0

    local_minimals.append(QAZcandidate(value=data[0]))

    for i in range(1,len(data)):

        if data[i] < local_minimals[local_minimals_last_minimal_index].value:
            # we overwrite the previous suspected local minimal
            if array_minimal_index + 1 == i:

                local_minimals[local_minimals_last_minimal_index] = QAZcandidate(value=data[i])

                array_minimal_index += 1

                continue

            else:
                # new candidate for a wining local minimum
                local_minimals.append(QAZcandidate(value=data[i]))

                local_minimals_last_minimal_index += 1

                array_minimal_index = i

                continue
        # data[i] > local_minimals[last_minimal_index].value
        else:
            # need to find maximum over all minimums which are smaller then data[i]
            max_smaller_minimum_element, max_smaller_minimum_element_index = find_max_smaller_minimum(local_minimals,data[i])

            # one candidate.
            if max_smaller_minimum_element is local_minimals[0]:

                local_minimals[local_minimals_last_minimal_index].rankDOWN += 1

            # last element
            elif max_smaller_minimum_element is local_minimals[local_minimals_last_minimal_index]:

                max_smaller_minimum_element.rankUP += 1

                max_smaller_minimum_element.rankDOWN += 1

            # element in the middle so improves position against previous elements and last minimum gains advantage against future elements
            else:

                max_smaller_minimum_element.rankUP += 1

                local_minimals[local_minimals_last_minimal_index].rankDOWN += 1

            # check if need to update winner
            if max_smaller_minimum_element is not local_minimals[0]:

                prev_candidate = local_minimals[max_smaller_minimum_element_index - 1]

                #we improve ranking
                if max_smaller_minimum_element.rankUP >= prev_candidate.rankDOWN:

                    local_minimals = local_minimals[0:max_smaller_minimum_element_index - 1] + local_minimals[max_smaller_minimum_element_index:]

                    local_minimals_last_minimal_index -= 1
            # max smaller minimum element is the first one so everybody gains
            else:
                pass

    x = local_minimals[0].value

    i = 0

    while data[i] != x:

        i += 1

    counter = 0

    j = i+1

    while j < len(data):

        if data[j] > x:

            counter += 1

        j += 1

    return counter, local_minimals[0].value

if __name__ == "__main__":

    import random

    for i in range(0,10):

        d = random.sample(range(1000), 1000)

        c1, val1 = qaz(d)

        c2, val2 = qaz_hard(d)

        if c1 != c2:

            print "error"
            print str(d)
            print "easy: qaz:"+str(c1)+" val:"+str(val1)
            print "hard: qaz:"+str(c2)+" val:"+str(val2)

        else:

            print "ok"

# n squared qaz solution
def qaz(data):

    n = len(data)

    max_counter = 0

    elements = []

    for i in range(0,n):

        candidate_counter = 0

        for j in range(i + 1,n):

            if data[j] > data[i]:

                candidate_counter += 1

        if candidate_counter > max_counter:

            max_counter = candidate_counter

            del elements[:]

            elements.append(data[i])

        elif candidate_counter == max_counter:

            elements.append(data[i])

    return max_counter, elements[0]









##### This is nlogn solution in case you replace the data structure which holds the local minimums with an AVL tree.
##### I did not use an AVL tree since it is easier to understand the solution this way.
##### in the worst case we are doing a binary search ~n times to find max over all candidates which is smaller then new value in case it is bigger the min over all minimums.
##### so nlogn in the worst case. This is not optimal since deleting from an array may result linear time while deleting from AVL will result logarithmic time.
##### a tester which validates against the trivial solution runs.
##### By the way it took a day to think about and implement.could not have done it in an interview.

class QAZcandidate(object):

    def __init__(self, value):

        self.value = value

        self.rankUP = 0

        self.rankDOWN = 0


def find_max_smaller_minimum(data,key, index=0):

    if len(data) == 0:

        return data[0], index

    middle = len(data)/2

    element = data[middle]

    if element.value > key:

        return find_max_smaller_minimum(data[middle:],key,index + middle)

    else:

        #element.value < key
        if middle > 0:

            if data[middle - 1].value < key:

                return find_max_smaller_minimum(data[0:middle],key,index)

            else:
                #we found max smaller minimum
                return data[middle], middle + index

        #element.value < key and its the largest minimum
        else:

            return data[middle], middle + index


def qaz_hard(data):

    if len(data) <= 1:

        return

    local_minimals = []

    local_minimals_last_minimal_index = 0

    array_minimal_index = 0

    local_minimals.append(QAZcandidate(value=data[0]))

    for i in range(1,len(data)):

        if data[i] < local_minimals[local_minimals_last_minimal_index].value:
            # we overwrite the previous suspected local minimal
            if array_minimal_index + 1 == i:

                local_minimals[local_minimals_last_minimal_index] = QAZcandidate(value=data[i])

                array_minimal_index += 1

                continue

            else:
                # new candidate for a wining local minimum
                local_minimals.append(QAZcandidate(value=data[i]))

                local_minimals_last_minimal_index += 1

                array_minimal_index = i

                continue
        # data[i] > local_minimals[last_minimal_index].value
        else:
            # need to find maximum over all minimums which are smaller then data[i]
            max_smaller_minimum_element, max_smaller_minimum_element_index = find_max_smaller_minimum(local_minimals,data[i])

            # one candidate.
            if max_smaller_minimum_element is local_minimals[0]:

                local_minimals[local_minimals_last_minimal_index].rankDOWN += 1

            # last element
            elif max_smaller_minimum_element is local_minimals[local_minimals_last_minimal_index]:

                max_smaller_minimum_element.rankUP += 1

                max_smaller_minimum_element.rankDOWN += 1

            # element in the middle so improves position against previous elements and last minimum gains advantage against future elements
            else:

                max_smaller_minimum_element.rankUP += 1

                local_minimals[local_minimals_last_minimal_index].rankDOWN += 1

            # check if need to update winner
            if max_smaller_minimum_element is not local_minimals[0]:

                prev_candidate = local_minimals[max_smaller_minimum_element_index - 1]

                #we improve ranking
                if max_smaller_minimum_element.rankUP >= prev_candidate.rankDOWN:

                    local_minimals = local_minimals[0:max_smaller_minimum_element_index - 1] + local_minimals[max_smaller_minimum_element_index:]

                    local_minimals_last_minimal_index -= 1
            # max smaller minimum element is the first one so everybody gains
            else:
                pass

    x = local_minimals[0].value

    i = 0

    while data[i] != x:

        i += 1

    counter = 0

    j = i+1

    while j < len(data):

        if data[j] > x:

            counter += 1

        j += 1

    return counter, local_minimals[0].value

if __name__ == "__main__":

    import random

    for i in range(0,10):

        d = random.sample(range(1000), 1000)

        c1, val1 = qaz(d)

        c2, val2 = qaz_hard(d)

        if c1 != c2:

            print "error"
            print str(d)
            print "easy: qaz:"+str(c1)+" val:"+str(val1)
            print "hard: qaz:"+str(c2)+" val:"+str(val2)

        else:

            print "ok"

Easy peasy.

Another approach is to build a binary search tree while adding the elements in the array from right to left (end to start). This works because:

1. Each time we go "down the tree" to the left all the elements in the tree above are larger than the current one so, add 1 + count the number of elements on the right side of the parent node.

2. When going "down the tree" to the right, the prev. element is small than the current one so don't count it.

3. For n elements we are traversing the tree which is max logN in height there for o(nlogn)

public int findMaxQaz(int[] buff) {

	int max = 0;
	int qaz = 0;

	// create the root
	TreeNode<int> root = new TreeNode(buff[buff.length-1]);
	TreeNode<int> node = root;

	for(int index=buff.length-2; index>=0; index--) {
		if(buff[index] < node.value) {
			qaz += countNodes(node.right);
			qaz += 1; // for current node
			if(node.left == null) {
				node.left = new TreeNode<int>(buff[indedx]);
				if(qaz > max)
					max = qaz;
			}
			else
				node = node.left;
		}
		else {
			if(mode.right == null) {
				node.right = node TreeNode<int>(buff[index]);
				if(qaz > max)
					max = qaz;
			}
			else
				node = node.right;
		}
	}

	return max;
}

private int countNodes(TreeNode node) {

	if(null == node)
		return 0;

	int left = countNodes(node.left);
	int right = countNodes(node.right);

	return left+right+1;
}

MAXIMUM-QUAZ ( int[] array )

1. MaxQaz = 0

2. Q = PRIORITY-QUEUE

3. for i = array.length - 1 to 0

4. index = Q.insert ( array [ i ] ) // return index of newly inserted element

5. qaz = Q.size - index

6. if ( qaz > MaxQaz )

7. MazQaz = qaz

8. return MazQaz

Here is a O(n) in python

def max_qaz(arr):
    qaz = {}
    max_qaz = -1
    for val in arr:
        for k, v in qaz.items():
            if val > k:
                qaz[k] += 1
                if qaz[k] > max_qaz:
                    max_qaz = qaz[k]

        qaz[val] = 0
    return max_qaz

public class id5649103830646784 {
	public static void main(String arcg[]){
		id5649103830646784 h = new id5649103830646784();
		int[] array = {33,25,26,58,41,59};
		pair[] array2 = new pair[array.length];
		for(int i=0;i<array.length;i++){
			array2[i] = h.new pair(array[i]);
		}
		h.sort(array2);
		for(int i=0;i<array2.length;i++){
			System.out.println(array2[i].val + ": " + array2[i].qaz);
		}
	}
	class pair{
		int val;
		int qaz;
		public pair(int val){
			this.val = val;
			qaz = 0;
		}
	}
	private pair[] array;
	private pair[] helper;
	void sort(pair[] array){
		this.array = array;
		this.helper = new pair[array.length];
		mergeSort(0,array.length-1);
	}
	void mergeSort(int low, int high){
		if(low < high){
			int mid = low+(high-low)/2;
			mergeSort(low, mid);
			mergeSort(mid+1, high);
			merge(low,mid,high);
		}
	}
	void merge(int low, int mid, int high){
		for(int i=low;i<=high;i++) helper[i] = array[i];
		int i=low, j=mid+1,k=low;
		while(i<=mid && j<=high){
			if(helper[i].val<=helper[j].val){
				array[k] = helper[i++];
				array[k].qaz += high-j+1;
			}
			else{
				array[k] = helper[j++];
			}
			k++;
		}
		while(i<=mid) array[k++] = helper[i++];
	}
}

public int findMaxqaz(List<Integer> input){
		int size = input.size();
		List<Integer> qaz = new ArrayList<>();
		Map<Integer,Integer> map = new HashMap<>(); 
		for(int i=0; i<input.size(); i++)
			map.put(input.get(i), size-i);
		List<Integer> sortedKeys = new ArrayList<>(map.keySet());
		Collections.sort(sortedKeys);
		for(int i=0; i<sortedKeys.size(); i++)
			qaz.add(Math.min(size-i, map.get(sortedKeys.get(i))));
		Collections.sort(qaz);
		return qaz.get(qaz.size()-1);
	}

#include <stdio.h>
#include <stdlib.h>

struct node {
  int val;
  int c_num;
  int l_num;
  struct node * left;
  int r_num;
  struct node * right;
};
struct node * root = NULL;

struct node * r_insert(struct node * root, int i) {
  // update # left and right children to maintain counters
  if (root == NULL) {
    struct node * n;
    n = (struct node *) malloc (sizeof(struct node));    
    n->val = i;
    n->c_num = 1;
    n->l_num = 0;
    n->r_num = 0;
    n->left = NULL;
    n->right = NULL;
    return n;
  }

  if (root->val < i) {
    root->left = r_insert(root->left, i);
    root->l_num++;    
  }  
  else if (root->val > i) {
    root->right = r_insert(root->right, i);
    root->r_num++;
  }
  else {
    root->c_num++;
  }

  return root;
}

int r_find(struct node * root, int i) {
  // TODO: Indicate error here
  if (root == NULL)
    return 0;

  if (root->val == i)
    return (root->c_num)-1;

  if (root->val < i) return r_find(root->left, i);
  else return root->c_num + root->l_num + r_find(root->right, i);
}

int insert_bin_src_tree(int i) {
  // Insert into decending ordetr btree; 
  root = r_insert(root, i);

  // qaz = rank in the btree's inorder traversal 
  return r_find(root, i);

}

// 33 , 25 , 26 , 58 , 41 , 59 
// 59;
// 59, 41 59->l+59->c+41->c-1 = 1; 
// 59, 41, 58: 0+0+1+0 = 1;
// 59, 41, 58, 26: 0+1+1+0+1= 3;

int qaz(int a[], int len) {
  int max_qaz=0, t;

  // Start from the last element; qaz = 0
  for (len--; len >=0; len--) {
    // Keep a binary search tree with # of children
    t = insert_bin_src_tree(a[len]);
    if ( t > max_qaz) max_qaz = t;      
  }
  return max_qaz;
}

int main (void) {
  int a[6] = {33 , 25 , 26 , 58 , 41 , 59};
  
  printf("max qaz %d\n", qaz(a, 6));
  return 0;
}

Can be done using two stacks

Modifed merge sort. We split array on tho subarrays and calculate local quaz for both subarray (divide phase). Then in merge phase (conquer pahse) with O(n) complexity update quaz of the whole array on the basis of already calculated values in divide phase.Original array is converted to one that is sorted but original indexes are stored.

int[] mergeQuaz(int[] input,int l,int r, int[] qaz) {
		if( l < r ) {
			int mid = l + (r - l)/ 2;
			int a[] = mergeQuaz(input,l,mid ,qaz);
		    int b[] = mergeQuaz(input,mid+1 ,r ,qa);
		    int indexA = 0;
		    int indexB = 0;		
		    int output[] = new int[a.length + b.length];
		    int outIndex = 0;
		    while (indexA < a.length) {
		    	if(indexB == b.length) {		    		
		    		qaz[a[indexA]] += b.length - indexB;
		    		output[outIndex] = a[indexA];	
		    		indexA++;
		    			    		
	    		} else {			
			    	if (input[a[indexA]]< input[b[indexB]]) {
			    		output[outIndex] = a[indexA]; 		
			    		qaz[a[indexA]] += b.length - indexB;
			    		indexB = 0;
			    		indexA++;
			    	} else {
			    		output[outIndex] = b[indexB];			    		
			    		indexB++;		    		
			    	}	
	    		}	
		    	outIndex++;
		    }
		    while(indexB<b.length) {
		    	output[outIndex] = b[indexB];		    	
		    	outIndex++;
		    	indexB++;
		    }
		    return output;
		}
		return new int[] {l};
	}

c#.
totally generic merge sort except of 1 line ( stressed in code).

static private Number[] MergeSort( Number[] arr ) {

    if ( arr.Length == 1 ) { return arr; }

    var leftHalf = new Number[ arr.Length / 2 ];
    var rightHalf = new Number[ arr.Length - arr.Length / 2 ];

    int t = 0;
    for ( int i = 0; i < arr.Length; i++ ) {
        if ( i < arr.Length / 2 ) { leftHalf[ i ] = arr[ i ]; }
        else { rightHalf[ t ] = arr[ i ]; t++; }
    }
    return Merge( MergeSort( leftHalf ), MergeSort( rightHalf ) );
}

static private Number[] Merge( Number[] arr1, Number[] arr2 ) {

    if ( arr1 == null ) { return arr2; }
    if ( arr2 == null ) { return arr1; }

    Number[] tail = null;

    if ( arr1.Length > 1 ) { tail = new Number[ arr1.Length - 1 ]; }

    if ( arr1[ 0 ].Value < arr2[ 0 ].Value ) {
        for ( int i = 0; i + 1 < arr1.Length; i++ ) {
            tail[ i ] = arr1[ i + 1 ];
        }
        arr1[ 0 ].qaz += arr2.Length; // the only one line added to merge sort
        return Concat( arr1[ 0 ], Merge( tail, arr2 ) );
    }

    tail = null;
    if ( arr2.Length > 1 ) { tail = new Number[ arr2.Length - 1 ]; }
    for ( int i = 0; i + 1 < arr2.Length; i++ ) {
        tail[i] = arr2[ i + 1 ];
    }

    return Concat( arr2[ 0 ], Merge( arr1, tail ) );
}

    private static Number[] Concat( Number firstElm, Number[] arr ) {
            
    var res = new Number[ arr.Length + 1 ];
    res[ 0 ] = firstElm;

    for ( int i = 0; i < arr.Length; i++ ) {
        res[ i + 1 ] = arr[ i ];
    }
    return res;
}
public struct Number {
    public int Value;
    public int qaz;
}

You can do this without mergesort.

1. For each number, make a new object storing that number and its index, and put them into another array
2. Sort this array according to the value of the objects.
3. Starting from the end, maintain a binary index tree storing the (original) indices. (By calling update(i, 1))
4. As we go along, find the number of (original) indices that we have seen that are greater than our current (original) index (log n using binary index tree, just compute sum(idx+1,n))
5. Keep a max value, updating it as we go.

O(nlogn) time, O(N) space. If we use out original array for the binary index tree, we only need one extra size n array.

using System;
class HelloWorld {
static void Main()
{
Console.WriteLine("enter the numbers:");
int num = int.Parse(Console.ReadLine());
int[] arr = new int[num];
for(int i = 0; i<num; i++)
{
int data = int.Parse(Console.ReadLine());
arr[i] = data;
}
int count=0;
for(int j = 0; j<num; j++)
{
for(int k=0; k<num; k++)
{
if(arr[j]< arr[k] && (j<k))
count++;
}
Console.WriteLine("qaz of"+"("+arr[j]+")"+"="+count);
count = 0;
}
}
}

using System;
class HelloWorld {
static void Main()
{
Console.WriteLine("enter the numbers:");
int num = int.Parse(Console.ReadLine());
int[] arr = new int[num];
for(int i = 0; i<num; i++)
{
int data = int.Parse(Console.ReadLine());
arr[i] = data;
}
int count=0;
for(int j = 0; j<num; j++)
{
for(int k=0; k<num; k++)
{
if(arr[j]< arr[k] && (j<k))
count++;
}
Console.WriteLine("qaz of"+"("+arr[j]+")"+"="+count);
count = 0;
}
}
}

Sort the given elements.
To find qaz(x), Find the number of elements to the right of the number in the sorted array( say p) and the number of elements to the right of the number in the original array(say q).
Then qaz(x) = min(p,q)

I was thinking about implementing this as a binary tree. Something along this lines in Pythonish pseudocode:

MAX_QAZ = 0

class Node:
    global MAX_QAZ

    def __init__(self, value):
        self.qaz = 0
        self.value = value
        self.right_child, self.left_child = None, None

    def insert(self, number):
        if number > self.value:
            if self.right_child is not None:
                self.right_child.insert(number) 
            else:
                self.right_child = Node(number)
            self.qaz += 1
            if self.qaz > MAX_QAZ:
                MAX_QAZ = self.qaz
            self.left_child.increment_childrens_qaz()
        else:
            if self.left_child is not None:
                self.left_child.insert(number)
            else:
                self.left_child = Node(number)

    def increment_childrens_qaz(self):
        self.qaz += 1
        if self.qaz > MAX_QAZ:
            MAX_QAZ = self.qaz
        self.left_child.increment_childrens_qaz()
        self.right_child.increment_childrens_qaz()


class BinaryTree:

    def insert(self, number):
        if self.root_node is None:
            self.root_node = Node(number)
            return
        self.root_node.insert(number)

tree = BinaryTree()
for number in list:
    tree.insert(number)
print MAX_QUAZ

Basically each time a node is inserted it's qaz is initialized to 0. If it's inserted to the left of existing node - existing node's qaz doesn't change. If it is inserted on the right of the existing node - existing node's qaz increments, and so does qaz of everything to the left of the existing node.

logic
build a binary tree rooted at first element. keep count of nodes to right of every node while building tree. visit every node
qaz (for number at node) = number of nodes to it's right + number of nodes to its' parents right (if parent is present) + 1 (if parent is present parent)

Find qaz from end of the array towards start as in the below psuedocode. qaz of last element is always 0.

if(arr[i-1]<=arr[i])
{qaz(i-1) = qaz(i)+1;}
else
{ int j=i;
//Increment j until until arr[i-1]<=arr[j]
qaz(i-1) = qaz(j)+1;
}

we could keep track of the max qaz in the process.

In the worst case, this could go to o(n2) though.

This is an O(n) solution.

public class MaxQaz {

	public static int findMaxQaz(int[] A) {

		int maxQaz = 0;
		int qaz = 0;

		if (A.length == 0 || A.length == 1) {
			return maxQaz;
		}
		int num = A[0];

		for (int i = 1; i < A.length; i++) {
			if (num < A[i]) { // As long as the previous number is less than
								// current keep counting
				qaz++;
			}

			if (num > A[i] || A.length - i == 1) { // if greater or reached end
				maxQaz = Math.max(qaz, maxQaz); // store the current count if it
												// is more than the max recorded
				qaz = 0; // Reset the count
				if ((A.length - i) < maxQaz) { // No need to continue if the
												// rest of the length is less
												// than maxqaz,
					break;
				}
				num = A[i]; // Use the current number to compare next
			}
		}
		return maxQaz;
	}

	public static void main(String[] args) {
		int[] array = { 50, 23, 42, 1, 2, 3, 4, 9, 83, 98, 33, 55, 21, 44 };
		//int[] array = { 33, 25, 26, 58, 41, 59 };

		System.out.println(MaxQaz.findMaxQaz(array));
	}
}

Build BST at the same time find maxQaz.

Maybe I didn't understand something, but I think about O(n) algorithm.

Step 1: Finding the x index of the max qaz

The number which has the max qaz should be the first number in the list that no number before is smaller than it. If there is a number before that is smaller than it so its qaz is greater. Therefore we should first move on the list and stop when we find a number that is bigger than the current minimum. The wanted index is the previous index(from our stop point in the list).

Step 2: Computing the qaz

After we find the index of the number with the max qaz, we just need to move on the rest of the list and count the number which are greater this number.

These two steps can be done with one run on the array, so it runs on O(n).
Feel free to correct me...