Find the Maximum Difference of Indices

Revision en21, by harsha314, 2021-08-08 14:13:04

Given an array $$$A$$$ of $$$N$$$ integers . Find the maximum of value of $$$i\ -\ j$$$ such that : $$$\newline$$$ $$$1)\ j\ <\ i \newline$$$ $$$2)\ A[j]\ <\ A[i] \newline$$$

Note : i and j are 0-based indices

Constraints : $$$ N \le 10^6 , A[i]\ \le\ 10^9\ for\ 0\ \le i\ \le\ N-1\newline $$$

Ex :

    <li>A = [1,2,3,4,5]
     j = 0 , i = 4 gives maximum difference of 4 satisfying the given conditions
     </li>
     <li>
     A = [8,4,8,7,6,6,3]
     j = 1 , i = 5 gives maximum difference of 4 satisfying the given conditions
     </li>
    Tags #array, #maximise

    History

     
     
     
     
    Revisions
     
     
      Rev. Lang. By When Δ Comment
    en35 English harsha314 2021-08-08 14:29:14 0 (published)
    en34 English harsha314 2021-08-08 14:28:56 7
    en33 English harsha314 2021-08-08 14:28:28 134 (saved to drafts)
    en32 English harsha314 2021-08-08 14:20:24 0 (published)
    en31 English harsha314 2021-08-08 14:19:00 4 Tiny change: 'N \le 10^6 , A[i]\ \le' -> 'N \le 10^6\ ;\ A[i]\ \le'
    en30 English harsha314 2021-08-08 14:18:36 9 Tiny change: 'traints : $ N \le 10' -> 'traints : \n<br/>\n$ N \le 10'
    en29 English harsha314 2021-08-08 14:18:17 4 Tiny change: 'n\nNote : i and j are 0-bas' -> 'n\nNote : $i$ and $j$ are 0-bas'
    en28 English harsha314 2021-08-08 14:17:27 8
    en27 English harsha314 2021-08-08 14:16:44 9
    en26 English harsha314 2021-08-08 14:16:07 9
    en25 English harsha314 2021-08-08 14:15:35 16
    en24 English harsha314 2021-08-08 14:14:44 13
    en23 English harsha314 2021-08-08 14:14:14 13 Tiny change: 'nditions\n A =' -> 'nditions\n</li>\n<li>\n A ='
    en22 English harsha314 2021-08-08 14:13:48 42
    en21 English harsha314 2021-08-08 14:13:04 56
    en20 English harsha314 2021-08-08 14:11:45 11
    en19 English harsha314 2021-08-08 14:10:38 4 Tiny change: 'le 10^6 , $\n$A[i]\ \le\' -> 'le 10^6 , A[i]\ \le\'
    en18 English harsha314 2021-08-08 14:10:15 8 Tiny change: '\ \le\ N-1 $\nEx : A' -> '\ \le\ N-1\newline $\nEx : A'
    en17 English harsha314 2021-08-08 14:09:43 33
    en16 English harsha314 2021-08-08 14:08:28 17
    en15 English harsha314 2021-08-08 14:06:48 14
    en14 English harsha314 2021-08-08 14:06:26 18
    en13 English harsha314 2021-08-08 14:04:41 4
    en12 English harsha314 2021-08-08 14:04:17 10
    en11 English harsha314 2021-08-08 14:02:02 4 Tiny change: 'aints : \nN <= 10^6 , \nA[i] <= 10' -> 'aints : \n- N <= 10^6 , \n- A[i] <= 10'
    en10 English harsha314 2021-08-08 14:01:08 9
    en9 English harsha314 2021-08-08 13:59:28 6
    en8 English harsha314 2021-08-08 13:58:29 12
    en7 English harsha314 2021-08-08 13:57:58 9 Tiny change: 'uch that :\n1) $j\ <' -> 'uch that : \newline\n1) $j\ <'
    en6 English harsha314 2021-08-08 13:57:32 9 Tiny change: ' $j\ <\ i\\ $\n2) $A[j' -> ' $j\ <\ i\newline$\n2) $A[j'
    en5 English harsha314 2021-08-08 13:57:08 1 Tiny change: '$j\ <\ i\\$\n2) $A[j' -> '$j\ <\ i\\ $\n2) $A[j'
    en4 English harsha314 2021-08-08 13:56:44 2 Tiny change: ') $j\ <\ i$\n2) $A[j' -> ') $j\ <\ i\\$\n2) $A[j'
    en3 English harsha314 2021-08-08 13:56:08 8
    en2 English harsha314 2021-08-08 13:55:28 12 Tiny change: ' value of i &mdash; j such that' -> ' value of $i\ -\ j$ such that'
    en1 English harsha314 2021-08-08 13:54:31 465 Initial revision (saved to drafts)