0 like 0 dislike
2,357 views
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,357 views

2 like 0 dislike

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;
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;
}

}
```
by
selected
1 like 0 dislike
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)
by Expert (113,040 points)
0 like 0 dislike
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.
by
1 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,333,322};

//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 .```
by
edited by anonymous
2 0
Actually time complexity of above will be O(nlogn)
As u have sorted an array