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 ofarr[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 < lint 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 functionsint 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 < ldef 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 Codeif __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 ofarr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l,given that the array has atleast 4 elements */// To represent minus infinitelet 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 < lfunction 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 codelet arr = [ 4, 8, 9, 2, 20 ];let n = arr.length;document.write(findMaxValue(arr, n));// This code is contributed by _saurabh_jaiswal</script> |
Output
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
This article is contributed by Rachit Belwariar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
