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 33 32

Output :  (33+32+5+6) is the maximum possible value .

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

Answer 1

#Find Largest and second largest element in the list and store their indexes

l = list(map(int,input().split()))
max1,max2,i,j = 0,0,0,0
for p in range(len(l)):
    if l[p] >= max1:
        max1 = l[p]
        i = p+1
for p in range(len(l)):
    if l[p] > max2 and l[p] != max1:
            max2 = l[p]
            j = p+1
if l.count(max1) > 1:
    ind = l.index(max1) + 1
    if ind > j:
        max2 = max1
        j = ind
print(max1+max2+i+j)

Answer 2

#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,33,32};       

        //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

(33+32+5+6) is the maximum possible value .

Answer 3

Algorithm:

1. We can divide a[i]+a[j]+i+j as (a[i]+i)+(a[j]+j)

2. Now for getting max value we need to add top two elements of a[i]+i

 Let me give more clarification by the code.......

 

Program:

Int Fun(int a[], int n){

        int max_1=0,max_2=0;

        for (int i=0;i<n;i++){

             if(a[i]+i > max_1){

                 max_2 = max_1;

                 max_1 = a[i]+i+1;

             }

         }

      return max_1+max_2;

}

Comments

Is your code working on case like :
12,1,2,3

---

Thank you for finding mistake in the code.
Just a small change is needed
max_1 = a[i]+i+1;

Answer 4

#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 ?
#solution:
# we have to maximize a[i] + i + a[j] + j , where i and j are index so i am adding index of elements to their values.
# now our target is to find two maximum values of the updated array,
# addition of two maximum values is desired answer.

# time complexity : O(N)
# space complexity : O(1)

arr=list(map(int,input().split()))
for i in range(len(arr)):
    arr[i] += i + 1

firstMax=max(arr)
secondMax=0

if arr.count(firstMax) > 1:
    secondMax=firstMax
else:
    for i in arr:
        if i > secondMax and i != firstMax:
            secondMax=i
print(firstMax + secondMax)