How to find the maximum value of (a[i] + a[j] + i - j ) over all the pairs (i,j) in an array in O(N) time ?

Question

Constraints :

1<=N<=1000000

1<=A[i]<=1000000000

Example :

4 6 12 18 333 322

Output :  (322+333+6-5) is the maximum possible value .

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

Answer 1

Approach:

• Iterate over an arr and overwrite each element by arr[i] = arr[i]+i
• Used min heap data structure with bound 2 so as to get max pair of element(Time complexity of inserting element in heap isO(logn)[worst case] ,similarly worst case time complexity is O(logn) best case isO(1))
• linear search to find respective index number of max pair
• computed ans using arr[max_index1]+arr[max_index2]-2*max_index2;
• Subtracted 2*max_index2; as we have to find arr[i]+arr[j]+i-j;

Complexity: 

1. Time Complexity: O(n) Linear time complexity
2. Space complexity : O(2) ------ as heap is bounded with 2 which is constant

 Code:

package com.desi.qna;

import java.util.Arrays;
import java.util.PriorityQueue;

public class ArraySum_ij {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[] = {4,6,12,18,333,322};
        get_sum_i_j(arr,arr.length);
    }

    private static void get_sum_i_j(int[] arr, int length) {
        int i;
        int max_index1 = 0,max_index2=0,ele1,ele2;
        PriorityQueue<Integer> min_heap = new PriorityQueue<Integer>();
        for(i=0;i<length;i++) {
            arr[i]+=i;
            min_heap.add(arr[i]);
            if(min_heap.size()>2) {
                min_heap.poll();
            }
        }
        ele1 = min_heap.poll();
        ele2 = min_heap.poll();
        max_index1 = linearSearch(arr, ele1,0,length);
        max_index2 = linearSearch(arr, ele2,0,length);
        int ans = arr[max_index1]+arr[max_index2]-2*max_index2; //j is first added and then subtracted
        System.out.println("arr["+max_index1+"] = "+(arr[max_index1]-max_index1)+" arr["+max_index2+"] = "+(arr[max_index2]-max_index2)+" i = "+max_index1+" j= "+max_index2);
        System.out.println("ans = "+ans);
    }

    private static int linearSearch(int[] arr, int ele, int i, int length) {
        // TODO Auto-generated method stub
        for(i=0;i<length;i++) {
            if(arr[i] == ele) {
                return i;
            }
        }
        return 0;
    }

}

Answer 2

So, for every 'i', consider a(i) + (i) and find maxiumum value of a(j)-j in the rest of the array in O(1) .
which can be done in O(1) by prefix and suffix maximas.

 

Time Complexity : O(N)

Space complexity : O(N)

Answer 3

1. We can use map STL in which all elements are inserted along with it's index.

2.after that traversing from last to second last  and then perform operation.

Answer 4

#Language - C#

# time complexity : O(1)

# space complexity : O(1)

Step1- Create a temporary array Copy the original array to temporary array.

Step2- Sort the original array

Step 3 - Take last two digits of sorted array (which are j and i) and get the index of those j and i in temporary array.

using System;

using System.Linq;

public class Test

{

    public static void Main()

    {

        int[] ar={4,6,12,18,333,322};       

        //To read input from console

        //int[] ar = Array.ConvertAll(Console.ReadLine().Split(' '),arraytemp => Convert.ToInt32(arraytemp));      

        int[] temp = new int[ar.Length];

        ar.CopyTo(temp,0);

        Array.Sort(ar);      

        Console.WriteLine("({0}+{1}+{2}-{3}) is the maximum possible value .",ar[ar.Length-1],ar[ar.Length-2],temp.ToList().IndexOf(ar[ar.Length-1])+1,temp.ToList().IndexOf(ar[ar.Length-2])+1);

    }

}

stdout

(333+322+5-6) is the maximum possible value .

Comments

Actually time complexity of above will be O(nlogn)
As u have sorted an array