A Distance Maximizing Problem | LeetCode
Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j].
http://yanhe.weebly.com/blog-for-studywork/leetcode-distance-maximizing-problem
int findLargestDistance(const int ary[], const int len)
{
int small[255];
int large[255];
small[0] = ary[0];
large[len-1] = ary[len-1];
for(int i=1;i<len;i++)
{
small[i] = small[i-1] < ary[i] ? small[i-1] : ary[i];
large[len-i-1] = large[len-i] > ary[len-i-1] ? large[len-i] : ary[len-i-1];
}
int i=0, j=0, max = -1;
while(i<len && j<len)
{
if (small[i] < large[j])
{
max = max > (j-i) ? max : (j-i);
j++;
}
else
i++;
}
return max;
}
https://techinterviewsolutions.net/2014/08/08/distance-maximizing-problem-java/
Using Stack: Ordered Stack
http://yanspace.net/Archive/2014/3/maximumji // the code will not work, need while loop
http://ideone.com/bA5w2v
先从左面扫一遍，当当前元素小于前面所有元素的时候压入堆栈，然后再从右面一次遍历，如果当前元素大于栈顶的元素，记录当前的j-i，并pop掉栈顶元素
Above diagram shows n lines sorted according its heights. Lines with same heights are sorted using its original index. We will also need to keep track of each line’s original index in order to calculate the distance later. Finally, we build a table by scanning the lines’ original index from right to left once.
http://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/
Brute Force O(N2)
Run two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.
https://askmecode.wordpress.com/2012/07/16/a-distance-maximizing-problem-ii/
Extend:
Given an array A, find maximum A[i]-A[j] where i<j
Read full article from A Distance Maximizing Problem | LeetCode
Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j].
Brute Force
For(dist=n-1; dist>=0; dist--)
for(i=0; i<n-dist; i++)
if(A[i+dist]>A[i]
return dist;
Observation
For input “5 2 3 1 7”,
3 never could be i which maximize j-I since 2 is
before 3.
1 never could be j since 1 is before 7
Idea:
Use lArray to store possible is.
Use rArray to store possible js.
Possible is
A=9 7 3 1 10 2 8 6 5 4
I=9 7 3 1
Iind=0 1 2 3
k=0
I[k]=A[0]
Iind[k]=0;
For(i=1;i<n;i++)
if(A[i]<I[k])
k=k+1;
I[k]=A[i]
Iind[k]=i;
Possible js
A=9 7 3 1 10 2 8 6 5 4
J= 10 6 5 4
Iind= 4 7 8 9
k=0
J[k]=A[n-1]
Jind[k]=n-1;
For(i=n-2;i>=0;i--)
if(A[i]>J[k])
k=k+1;
J[k]=A[i]
Jind[k]=i;
Queue Q to store Iind
Stack S to store Jind
maxDist=0;
While(S is not empty)
jInd=S.pop();
while(Q is not empty)
iInd=Q.front();
if(A[jInd]>A[iInd])
maxDist=(jInd-iInd>maxDist)?jInd-iInd:maxDist;
break;
else
Q.deque();
For(dist=n-1; dist>=0; dist--)
for(i=0; i<n-dist; i++)
if(A[i+dist]>A[i]
return dist;
Observation
For input “5 2 3 1 7”,
3 never could be i which maximize j-I since 2 is
before 3.
1 never could be j since 1 is before 7
Idea:
Use lArray to store possible is.
Use rArray to store possible js.
Possible is
A=9 7 3 1 10 2 8 6 5 4
I=9 7 3 1
Iind=0 1 2 3
k=0
I[k]=A[0]
Iind[k]=0;
For(i=1;i<n;i++)
if(A[i]<I[k])
k=k+1;
I[k]=A[i]
Iind[k]=i;
Possible js
A=9 7 3 1 10 2 8 6 5 4
J= 10 6 5 4
Iind= 4 7 8 9
k=0
J[k]=A[n-1]
Jind[k]=n-1;
For(i=n-2;i>=0;i--)
if(A[i]>J[k])
k=k+1;
J[k]=A[i]
Jind[k]=i;
Queue Q to store Iind
Stack S to store Jind
maxDist=0;
While(S is not empty)
jInd=S.pop();
while(Q is not empty)
iInd=Q.front();
if(A[jInd]>A[iInd])
maxDist=(jInd-iInd>maxDist)?jInd-iInd:maxDist;
break;
else
Q.deque();
Best Solution O(N)
eliminate all unnecessary comparisons.
Please look at the above diagram carefully, and ask yourself if you would choose index a or b as a potential starting point. Clearly, you would never choose index b as the starting point. Why?
Assume that choosing index b as the starting point, the max distance is j-b, where A[j] > A[b]. Now, since a < b and A[a] is not taller than A[b] which implies that A[j] > A[a], we can form a farther distance by choosing a as the starting index. Therefore, we cannot choose b as the starting point as this forms a contradiction.
Generally, we want to choose only starting points with no such lines that are shorter to its left side. From the diagram above, only lines of index 0, 1, 3, 4 are valid starting points.
To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j.
For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index.
So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.
int maxIndexDiff(int arr[], int n){ int maxDiff; int i, j; int *LMin = (int *)malloc(sizeof(int)*n); int *RMax = (int *)malloc(sizeof(int)*n); /* Construct LMin[] such that LMin[i] stores the minimum value from (arr[0], arr[1], ... arr[i]) */ LMin[0] = arr[0]; for (i = 1; i < n; ++i) LMin[i] = min(arr[i], LMin[i-1]); /* Construct RMax[] such that RMax[j] stores the maximum value from (arr[j], arr[j+1], ..arr[n-1]) */ RMax[n-1] = arr[n-1]; for (j = n-2; j >= 0; --j) RMax[j] = max(arr[j], RMax[j+1]); /* Traverse both arrays from left to right to find optimum j - i This process is similar to merge() of MergeSort */ i = 0, j = 0, maxDiff = -1; while (j < n && i < n) { if (LMin[i] < RMax[j]) { maxDiff = max(maxDiff, j-i); j = j + 1; } else i = i+1; } return maxDiff;}int findLargestDistance(const int ary[], const int len)
{
int small[255];
int large[255];
small[0] = ary[0];
large[len-1] = ary[len-1];
for(int i=1;i<len;i++)
{
small[i] = small[i-1] < ary[i] ? small[i-1] : ary[i];
large[len-i-1] = large[len-i] > ary[len-i-1] ? large[len-i] : ary[len-i-1];
}
int i=0, j=0, max = -1;
while(i<len && j<len)
{
if (small[i] < large[j])
{
max = max > (j-i) ? max : (j-i);
j++;
}
else
i++;
}
return max;
}
https://techinterviewsolutions.net/2014/08/08/distance-maximizing-problem-java/
Using Stack: Ordered Stack
http://yanspace.net/Archive/2014/3/maximumji // the code will not work, need while loop
http://ideone.com/bA5w2v
先从左面扫一遍，当当前元素小于前面所有元素的时候压入堆栈，然后再从右面一次遍历，如果当前元素大于栈顶的元素，记录当前的j-i，并pop掉栈顶元素
public int maxDistance(int[] A) {
Stack stk = new Stack();
for(int i = 0; i < A.length; i++){
if(st.isEmpty() || A[i] < st.peek()){
st.push(i);
}
}
int maxLen = 0;
for (int i = A.length - 1; i >= maxLen; i--) {
while (!stk.empty() && A[stk.peek()] < A[i]) { // here need while loop, time complexity: O(m+n), m is the len of the stack
maxLen = Math.max(maxLen, i - stk.peek());
stk.pop();
}
}
return maxLen;
}
Sorting O(N log N)
Above diagram shows n lines sorted according its heights. Lines with same heights are sorted using its original index. We will also need to keep track of each line’s original index in order to calculate the distance later. Finally, we build a table by scanning the lines’ original index from right to left once.
Notice that once we sorted the lines, we are able to find the maximum distance in O(N) time.
For each possible original starting index i, we find the original ending index j, which is the maximum among all j’s where A[j] > A[i].
To enable the quick search for the maximum, we can build a look up table in O(N) time by scanning from right to left once. For example, we start with index i = 4, which is the shortest line. We know the maximum of all original indices to the right is 7, therefore max distance = 7 – 4 = 3. For the next line which original index is 3, the max distance = 7 – 3 = 4. Now, we must skip over the duplicates and reach the line with its original index 1. Here, we must be careful to skip over all duplicate heights which are not part of the solution because not satisfying the constraint A[j] > A[i]. Therefore, the max distance for this case = 2 – 1 = 1.
http://www.careercup.com/question?id=11532811http://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/
Brute Force O(N2)
Run two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.
int maxIndexDiff(int arr[], int n){ int maxDiff = -1; int i, j; for (i = 0; i < n; ++i) { for (j = n-1; j > i; --j) { if(arr[j] > arr[i] && maxDiff < (j - i)) maxDiff = j - i; } } return maxDiff;}https://askmecode.wordpress.com/2012/07/16/a-distance-maximizing-problem-ii/
Extend:
Given an array A, find maximum A[i]-A[j] where i<j
Read full article from A Distance Maximizing Problem | LeetCode
