0 like 0 dislike
291 views
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 .
| 291 views

## 4 Answers

0 like 0 dislike
```#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)```
by (180 points)
0 like 0 dislike
```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;

}```
by (230 points)
edited
1 0
Is your code working on case like :
12,1,2,3
1 0
Thank you for finding mistake in the code.
Just a small change is needed
max_1 = a[i]+i+1;
0 like 0 dislike
```#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 .```
by
0 like 0 dislike
#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)
by