Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
Constraints :



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 .
in Algorithms and Problems by Expert (107,750 points) | 2,143 views

4 Answers

2 like 0 dislike
Best answer


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


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



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

    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++) {
            if(min_heap.size()>2) {
        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;

selected by
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 (107,750 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.
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};       

        //To read input from console

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

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



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




(333+322+5-6) is the maximum possible value .
edited by anonymous
2 0
Actually time complexity of above will be O(nlogn)
As u have sorted an array