Maximize arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l
Maximize arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l. Find the maximum value of arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l
Example:
Let us say our array is {4, 8, 9, 2, 20} Then the maximum such value is 23 (9 - 4 + 20 - 2)
Brute Force Method:
We can simply find all the combinations of size 4 with given constraints. The maximum value will be the required answer. This method is very inefficient.
Efficient Method (Dynamic Programming):
We will use Dynamic Programming to solve this problem. For this we create four 1-Dimensional DP tables. Let us say there are four DP tables as – table1[], table2[], table3[], table4[] Then to find the maximum value of arr[l] – arr[k] + arr[j] – arr[i], such that i < j < k < l table1[] should store the maximum value of arr[l] table2[] should store the maximum value of arr[l] – arr[k] table3[] should store the maximum value of arr[l] – arr[k] + arr[j] table4[] should store the maximum value of arr[l] – arr[k] + arr[j] – arr[i] Then the maximum value would be present in index 0 of table4 which will be our required answer.
Below is the implementation of above idea:
C++
/* A C++ Program to find maximum value of arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l, given that the array has atleast 4 elements */ #include <bits/stdc++.h> using namespace std; // To represent minus infinite #define MIN -100000000 // A Dynamic Programming based function to find maximum // value of arr[l] - arr[k] + arr[j] - arr[i] is maximum // and i < j < k < l int findMaxValue( int arr[], int n) { // If the array has less than 4 elements if (n < 4) { printf ( "The array should have atleast 4 elements\n" ); return MIN; } // We create 4 DP tables int table1[n + 1], table2[n], table3[n - 1], table4[n - 2]; // Initialize all the tables to MIN for ( int i=0; i<=n; i++) table1[i] = table2[i] = table3[i] = table4[i] = MIN; // table1[] stores the maximum value of arr[l] for ( int i = n - 1; i >= 0; i--) table1[i] = max(table1[i + 1], arr[i]); // table2[] stores the maximum value of arr[l] - arr[k] for ( int i = n - 2; i >= 0; i--) table2[i] = max(table2[i + 1], table1[i + 1] - arr[i]); // table3[] stores the maximum value of arr[l] - arr[k] // + arr[j] for ( int i = n - 3; i >= 0; i--) table3[i] = max(table3[i + 1], table2[i + 1] + arr[i]); // table4[] stores the maximum value of arr[l] - arr[k] // + arr[j] - arr[i] for ( int i = n - 4; i >= 0; i--) table4[i] = max(table4[i + 1], table3[i + 1] - arr[i]); /*for (int i = 0; i < n + 1; i++) cout << table1[i] << " " ; cout << endl; for (int i = 0; i < n; i++) cout << table2[i] << " " ; cout << endl; for (int i = 0; i < n - 1; i++) cout << table3[i] << " " ; cout << endl; for (int i = 0; i < n - 2; i++) cout << table4[i] << " " ; cout << endl; */ // maximum value would be present in table4[0] return table4[0]; } // Driver Program to test above functions int main() { int arr[] = { 4, 8, 9, 2, 20 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "%d\n" , findMaxValue(arr, n)); return 0; } |
Java
/* A Java Program to find maximum value of arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l, given that the array has atleast 4 elements */ import java.util.Arrays; class GFG { // A Dynamic Programming based function // to find maximum value of // arr[l] - arr[k] + arr[j] - arr[i] // is maximum and i < j < k < l static int findMaxValue( int [] arr, int n) { // If the array has less than 4 elements if (n < 4 ) { System.out.println( "The array should have" + " atleast 4 elements" ); } // We create 4 DP tables int table1[] = new int [n + 1 ]; int table2[] = new int [n]; int table3[] = new int [n - 1 ]; int table4[] = new int [n - 2 ]; // Initialize all the tables to minus Infinity Arrays.fill(table1, Integer.MIN_VALUE); Arrays.fill(table2, Integer.MIN_VALUE); Arrays.fill(table3, Integer.MIN_VALUE); Arrays.fill(table4, Integer.MIN_VALUE); // table1[] stores the maximum value of arr[l] for ( int i = n - 1 ; i >= 0 ; i--) { table1[i] = Math.max(table1[i + 1 ], arr[i]); } // table2[] stores the maximum value of // arr[l] - arr[k] for ( int i = n - 2 ; i >= 0 ; i--) { table2[i] = Math.max(table2[i + 1 ], table1[i + 1 ] - arr[i]); } // table3[] stores the maximum value of // arr[l] - arr[k] + arr[j] for ( int i = n - 3 ; i >= 0 ; i--) table3[i] = Math.max(table3[i + 1 ], table2[i + 1 ] + arr[i]); // table4[] stores the maximum value of // arr[l] - arr[k] + arr[j] - arr[i] for ( int i = n - 4 ; i >= 0 ; i--) table4[i] = Math.max(table4[i + 1 ], table3[i + 1 ] - arr[i]); return table4[ 0 ]; } // Driver Code public static void main(String[] args) { int arr[] = { 4 , 8 , 9 , 2 , 20 }; int n = arr.length; System.out.println(findMaxValue(arr, n)); } } // This code is contributed by Vivekkumar Singh |
Python3
# A Python3 Program to find maximum value of # arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l, # given that the array has atleast 4 elements # A Dynamic Programming based function to find # maximum value of arr[l] - arr[k] + arr[j] - arr[i] # is maximum and i < j < k < l def findMaxValue(arr, n): # If the array has less than 4 elements if n < 4 : print ( "The array should have atleast 4 elements" ) return MIN # We create 4 DP tables table1, table2 = [ MIN ] * (n + 1 ), [ MIN ] * n table3, table4 = [ MIN ] * (n - 1 ), [ MIN ] * (n - 2 ) # table1[] stores the maximum value of arr[l] for i in range (n - 1 , - 1 , - 1 ): table1[i] = max (table1[i + 1 ], arr[i]) # table2[] stores the maximum # value of arr[l] - arr[k] for i in range (n - 2 , - 1 , - 1 ): table2[i] = max (table2[i + 1 ], table1[i + 1 ] - arr[i]) # table3[] stores the maximum value of # arr[l] - arr[k] + arr[j] for i in range (n - 3 , - 1 , - 1 ): table3[i] = max (table3[i + 1 ], table2[i + 1 ] + arr[i]) # table4[] stores the maximum value of # arr[l] - arr[k] + arr[j] - arr[i] for i in range (n - 4 , - 1 , - 1 ): table4[i] = max (table4[i + 1 ], table3[i + 1 ] - arr[i]) # maximum value would be present in table4[0] return table4[ 0 ] # Driver Code if __name__ = = "__main__" : arr = [ 4 , 8 , 9 , 2 , 20 ] n = len (arr) # To represent minus infinite MIN = - 100000000 print (findMaxValue(arr, n)) # This code is contributed by Rituraj Jain |
C#
// C# Program to find maximum value of // arr[l] - arr[k] + arr[j] - arr[i] // and i < j < k < l, given that // the array has atleast 4 elements using System; class GFG { // A Dynamic Programming based function // to find maximum value of // arr[l] - arr[k] + arr[j] - arr[i] // is maximum and i < j < k < l static int findMaxValue( int [] arr, int n) { // If the array has less than 4 elements if (n < 4) { Console.WriteLine( "The array should have" + " atleast 4 elements" ); } // We create 4 DP tables int []table1 = new int [n + 1]; int []table2 = new int [n]; int []table3 = new int [n - 1]; int []table4 = new int [n - 2]; // Initialize all the tables to minus Infinity fill(table1, int .MinValue); fill(table2, int .MinValue); fill(table3, int .MinValue); fill(table4, int .MinValue); // table1[] stores the maximum value of arr[l] for ( int i = n - 1; i >= 0; i--) { table1[i] = Math.Max(table1[i + 1], arr[i]); } // table2[] stores the maximum value of // arr[l] - arr[k] for ( int i = n - 2; i >= 0; i--) { table2[i] = Math.Max(table2[i + 1], table1[i + 1] - arr[i]); } // table3[] stores the maximum value of // arr[l] - arr[k] + arr[j] for ( int i = n - 3; i >= 0; i--) table3[i] = Math.Max(table3[i + 1], table2[i + 1] + arr[i]); // table4[] stores the maximum value of // arr[l] - arr[k] + arr[j] - arr[i] for ( int i = n - 4; i >= 0; i--) table4[i] = Math.Max(table4[i + 1], table3[i + 1] - arr[i]); return table4[0]; } static void fill( int [] arr, int val) { for ( int i = 0; i < arr.Length; i++) arr[i] = val; } // Driver Code public static void Main(String[] args) { int []arr = { 4, 8, 9, 2, 20 }; int n = arr.Length; Console.WriteLine(findMaxValue(arr, n)); } } // This code is contributed by Princi Singh |
Javascript
<script> /* A Javascript program to find maximum value of arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l, given that the array has atleast 4 elements */ // To represent minus infinite let MIN = -100000000 // A Dynamic Programming based function to // find maximum value of arr[l] - arr[k] // + arr[j] - arr[i] is maximum and // i < j < k < l function findMaxValue(arr, n) { // If the array has less than 4 elements if (n < 4) { document.write( "The array should have " + "atleast 4 elements\n" ); return MIN; } // We create 4 DP tables let table1 = new Array(n + 1); let table2 = new Array(n); let table3 = new Array(n - 1); let table4 = new Array(n - 2); // Initialize all the tables to MIN for (let i = 0; i <= n; i++) table1[i] = table2[i] = table3[i] = table4[i] = MIN; // table1[] stores the maximum value of arr[l] for (let i = n - 1; i >= 0; i--) table1[i] = Math.max(table1[i + 1], arr[i]); // table2[] stores the maximum value // of arr[l] - arr[k] for (let i = n - 2; i >= 0; i--) table2[i] = Math.max(table2[i + 1], table1[i + 1] - arr[i]); // table3[] stores the maximum value of // arr[l] - arr[k] + arr[j] for (let i = n - 3; i >= 0; i--) table3[i] = Math.max(table3[i + 1], table2[i + 1] + arr[i]); // table4[] stores the maximum value of // arr[l] - arr[k] + arr[j] - arr[i] for (let i = n - 4; i >= 0; i--) table4[i] = Math.max(table4[i + 1], table3[i + 1] - arr[i]); /*for (int i = 0; i < n + 1; i++) cout << table1[i] << " " ; cout << endl; for (int i = 0; i < n; i++) cout << table2[i] << " " ; cout << endl; for (int i = 0; i < n - 1; i++) cout << table3[i] << " " ; cout << endl; for (int i = 0; i < n - 2; i++) cout << table4[i] << " " ; cout << endl; */ // Maximum value would be present in table4[0] return table4[0]; } // Driver code let arr = [ 4, 8, 9, 2, 20 ]; let n = arr.length; document.write(findMaxValue(arr, n)); // This code is contributed by _saurabh_jaiswal </script> |
23
Time Complexity : O(n), where n is the size of input array
Auxiliary Space : Since we are creating four tables to store our values, space is 4*O(n) = O(4*n) = O(n)
Exercise for the readers:
This problem is simple yet powerful. The problem can be generalized to any expression under the given conditions. Find the maximum value of arr[j] – 2*arr[i] + 3*arr[l] – 7*arr[k], such that i < j < k < l
Contact Us