{"id":494,"date":"2020-06-10T11:26:08","date_gmt":"2020-06-10T11:26:08","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=494"},"modified":"2022-12-13T11:08:06","modified_gmt":"2022-12-13T11:08:06","slug":"find-maximum","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/find-maximum\/","title":{"rendered":"Find Maximum"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Arrays<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given an array A<\/code> of N<\/code> positive integers. The task is to find the maximum<\/code> of
\nj - i<\/code> such that A[j] > A[i]<\/code>, where j > i<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
Input : N = 10, A[] = [5 16 7 3 2 9 10 4 3 4]\n\nOutput : 6\n\nExplanation : \n\n16 > 5, diff = 1 - 0 = 1\n7 > 5,  diff = 2 - 0 = 2\n9 > 5,  diff = 5 - 0 = 5\n9 > 7,  diff = 5 - 2 = 3\n10 > 5, diff = 6 - 0 = 6\n4 > 2,  diff = 7 - 4 = 1\n3 > 2,  diff = 8 - 4 = 4\n4 > 2,  diff = 9 - 4 = 5\n\nOut of all these differences, 6 was the maximum difference between indexes of 5 and 10 i.e. 6 - 0 = 6<\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
BRUTE FORCE METHOD:<\/h4>\n
\n
    \n
  1. \n
    This method is Simple<\/code> but Inefficient<\/code>.  <\/p>\n<\/li>\n
  2. \n
    Run two nested loops.<\/p>\n<\/li>\n
  3. \n
    In the outer loop, pick elements one by one from left to right.<\/p>\n<\/li>\n
  4. \n
    In the inner loop, pick the rest of the elements and keep comparing the maximum<\/code> value of (j-i)<\/code>.<\/p>\n<\/li>\n
  5. \n
    Time complexity<\/code> of this approach is O(N2<\/sup>). <\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    EFFICIENT METHOD:<\/h4>\n
    \n
      \n
    1. \n
      The problem can be solved by simply finding out two Optimum Indexes<\/code> of the array, left index<\/code> i<\/code> and right index<\/code> j<\/code>. <\/p>\n<\/li>\n
    2. \n
      For an element A[i]<\/code>, we need not consider it for the left index if there exists a smaller element than A[i]<\/code> on its left side.<\/p>\n<\/li>\n
    3. \n
      Similarly for an element A[i]<\/code>, we need not consider it for the right index if there exits a greater element on its right side.<\/p>\n<\/li>\n
    4. \n
      Now construct two arrays : leftMin[]<\/code> and rightMax[]<\/code>,
      \nsuch that leftMin[i]<\/code> contains the smallest element on its left side including itself and rightMax[i]<\/code> contains the largest element on its right side including itself.<\/p>\n<\/li>\n
    5. \n
      Start traversing both the arrays from left to right.<\/p>\n<\/li>\n
    6. \n
      While traversing :-<\/p>\n
      \n
      if leftMin[i]<\/code> ><\/code> rightMax[i]<\/code>, then we simply move ahead in leftMin[]<\/code> by 1<\/code>, as all elements to the left of leftMin[i]<\/code> are either greater than or equal to leftMin[i]<\/code><\/p>\n<\/blockquote>\n<\/li>\n<\/ol>\n
      \n
      if leftMin[i]<\/code> <<\/code> rightMax[i]<\/code>, then we move ahead in rightMax[i]<\/code> to look for a better value of j-i<\/code>.<\/p>\n<\/blockquote>\n<\/blockquote>\n
      SOLUTIONS:<\/h3>\n\t\t\t\t\t\t