avimum Left Range. The maxLeftRange for an array is the maximum value of the dif

Question

avimum Left Range. The maxLeftRange for an array is the maximum value of the difference between an entry and an entry to its left. For example, the uALE Range of (3, 1,4,1, 5, 9, 2) is 8 because the difference between the 9 and the 1s to its left is 8 and no other difference between an entry and another entry to its left is greater. As another example the maxLeftRange of [9. 4,6,8, 2, 2) is 4. Write a function that returns the maxLeftRange of an integer array. View Menu This function should work in linear time. Points off for worse than linear time. You may not use hashing. Indicate the running time of your function.

Explanation / Answer

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main
{
   public static void main (String[] args) throws java.lang.Exception
   {
       // your code goes here
       int arr[] = {1,1,1,1,2,2};
       Stack st = new Stack();
       int max_left_range = -1;
      
       st.push(arr[0]);
for(int i=1;i<arr.length;i++){
   int tope = (Integer) st.peek();
   if(tope > arr[i]){
       st.pop();
       st.push(arr[i]);
   }else{
       int range = arr[i] - tope;
       if(range>max_left_range){
           max_left_range = range;
       }
   }
}
System.out.println(max_left_range);
   }
}

Explanation:

We solve this problem using the concept of Stacks. First push the first element of the the array into the stack. Then we traverse the array if array element is less than that at the top remove the element at top and push that array element in the stack. Otherwise, if array element is greater than that at the top of the stack calculate the difference and check it with the max_left_range. If it's greater swap these otherwise move forward.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.