Given an array arr[] of size, N, the task is to maximize the score to reduce the array to a single element by replacing any subarray with its sum where the score of one such operation is the product of subarray length and the minimum value of that subarray.
Examples:
Input: N = 2, arr[] = {1, 5}
Output: 2
Explanation: Select subarray (0, 1). Then array arr[] become { 6 } and points earned = 2 * min(1, 5) = 2. Total points earned = 2Input: N = 3, arr[] = {2, 3, 5}
Output: 14
Explanation: First select subarray (0, 1), then array arr[] become { 5, 5 } and points earned = 2 * min(2, 3) = 4. Select subarray (0, 1), then array arr[] become { 10 } and points earned = 2* min(5, 5) = 10. Total points earned = 4 + 10 =14.
Approach using Prefix Sum and DP (Memoization):
The Basic idea to solve this problem statement is to maintain a prefix sum array and obtain sum between range using DP (memoization).
Let there be three elements in the subarray {a, b, c} with b > a > c.
1st Case: If we include all the element at a time. array becomes {a+b+c}, points reward = 3*min(a, b, c) = 3*c.
2nd Case: Now, take two element at a time,
First select subarray(1, 2), array becomes (a, b+c), points reward = 2 * min(b, c) = 2*c
Now select subarray(0, 1), array becomes (a+b+c), points reward = 2 * min(a, b+c) = 2*a
Total points obtained = 2*c + 2*aNow, points obtained in the 2nd case is more than points obtained in the first case as
a > c So 2*a > c. So it is optimal to not choose all of the three at a time and break it into two parts from b. This can be implemented with the help of dynamic programming to store the maximum possible point for a subarray [i, j] for avoiding repeated calculation.
Follow the steps mentioned below to implement the idea:
- Create a prefix sum array pre[] to obtain the sum between any range in O(1) time.
- Create a recursive function that takes i and j as parameters that determines the range of a group.
- Iterate from k = i to j to partition the given range into two groups.
- Call the recursive function for these groups.
- Suppose ans1and ans2 represents the total points obtained from the left and the right part respectively.
- Now for the current partition at index k, the potential answer will be ans1 + ans2 + 2* min(left element, right element) as seen from the above discussion.
- Now left element will be pre[k+1]-pre[i], the right element will be pre[j-1] – pre[k+1], which can be computed in O(1) time from the prefix sum array.
- The Maximum value obtained for the range 0 to N-1 is the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// dp array to store repeated statelong long dp[100][100];// Function to find the maximum possible pointslong long maxPoint(int i, int j, vector<long long>& arr, vector<long long>& temp){ // Base case if (i >= j) return 0; if (j - i == 1) return 2 * min(arr[i], arr[j]); if (dp[i][j] != -1) return dp[i][j]; long long ans = 0; for (int k = i; k < j; k++) { // Points rewarded for left subarray long long ans1 = maxPoint(i, k, arr, temp); // Points rewarded for right subarray long long ans2 = maxPoint(k + 1, j, arr, temp); long long left_element = temp[k + 1] - temp[i]; long long right_element = temp[j + 1] - temp[k + 1]; long long total = ans1 + ans2 + min(left_element, right_element) * 2; // Total points for partition at current index ans = max(total, ans); } // Store the ans in dp state and return the ans return dp[i][j] = ans;}int findMax(vector<long long>& arr, int N){ vector<long long> temp; temp.push_back(0); // To store sum of each elements long long s = 0; for (int i = 0; i < N; i++) { s += arr[i]; temp.push_back(s); } // Initializing DP array with -1 memset(dp, -1, sizeof(dp)); return maxPoint(0, N - 1, arr, temp);}// Driver Codeint main(){ vector<long long> arr = { 2, 3, 5 }; int N = arr.size(); // Function call int ans = findMax(arr, N); cout << ans; return 0;} |
Java
// Java code to implement the approachpublic class gfg2 { // dp array to store repeated state static long[][] dp = new long[100][100]; // Function to find the maximum possible points static long maxPoint(int i, int j, long[] arr, long[] temp) { // Base case if (i >= j) return 0; if (j - i == 1) return 2 * Math.min(arr[i], arr[j]); if (dp[i][j] != -1) return dp[i][j]; long ans = 0; for (int k = i; k < j; k++) { // Points rewarded for left subarray long ans1 = maxPoint(i, k, arr, temp); // Points rewarded for right subarray long ans2 = maxPoint(k + 1, j, arr, temp); long left_element = temp[k + 1] - temp[i]; long right_element = temp[j + 1] - temp[k + 1]; long total = ans1 + ans2 + Math.min(left_element, right_element) * 2; // Total points for partition at current index ans = Math.max(total, ans); } // Store the ans in dp state and return the ans return dp[i][j] = ans; } static long findMax(long[] arr, int N) { // vector<long long> temp; // temp.push_back(0); long[] temp = new long[N + 1]; // To store sum of each elements long s = 0; for (int i = 0; i < N; i++) { s += arr[i]; temp[i + 1] = s; } // Initializing DP array with -1 for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[0].length; j++) { dp[i][j] = -1; } } return maxPoint(0, N - 1, arr, temp); } // Driver Code public static void main(String[] args) { long[] arr = { 2, 3, 5 }; int N = arr.length; // Function call long ans = findMax(arr, N); System.out.println(ans); }}// This code is contributed by karandeep1234 |
Python3
#Python code to implement the approach# dp array to store repeated statedp=[[0 for i in range(100)] for j in range(100)]# Function to find the maximum possible pointsdef maxPoint(i,j,arr,temp): # Base case if(i>=j): return 0 if(j-i==1): return 2 * min(arr[i], arr[j]) if(dp[i][j] != -1): return dp[i][j] ans=0 for k in range(i,j): # Points rewarded for left subarray ans1 = maxPoint(i, k, arr, temp) # Points rewarded for right subarray ans2 = maxPoint(k + 1, j, arr, temp) left_element = temp[k + 1] - temp[i] right_element = temp[j + 1] - temp[k + 1] total=ans1 + ans2 + min(left_element, right_element) * 2 # Total points for partition at current index ans = max(total, ans) # Store the ans in dp state and return the ans dp[i][j] = ans return dp[i][j] def findMax(arr,N): temp=[] temp.append(0) # To store sum of each elements s=0 for i in range(N): s=s+arr[i] temp.append(s) # Initializing DP array with -1 for i in range(len(dp)): for j in range(len(dp[0])): dp[i][j]=-1 return maxPoint(0, N - 1, arr, temp) # Driver Codearr=[2,3,5]N=len(arr)# Function callans=findMax(arr,N)print(ans)# This code is contributed by Pushpesh Raj. |
C#
// C# code to implement the approachusing System;public class GFG { // dp array to store repeated state static long[, ] dp = new long[100, 100]; // Function to find the maximum possible points static long maxPoint(int i, int j, long[] arr, long[] temp) { // Base case if (i >= j) return 0; if (j - i == 1) return 2 * Math.Min(arr[i], arr[j]); if (dp[i, j] != -1) return dp[i, j]; long ans = 0; for (int k = i; k < j; k++) { // Points rewarded for left subarray long ans1 = maxPoint(i, k, arr, temp); // Points rewarded for right subarray long ans2 = maxPoint(k + 1, j, arr, temp); long left_element = temp[k + 1] - temp[i]; long right_element = temp[j + 1] - temp[k + 1]; long total = ans1 + ans2 + Math.Min(left_element, right_element) * 2; // Total points for partition at current index ans = Math.Max(total, ans); } // Store the ans in dp state and return the ans return dp[i, j] = ans; } static long findMax(long[] arr, int N) { // vector<long long> temp; // temp.push_back(0); long[] temp = new long[N + 1]; // To store sum of each elements long s = 0; for (int i = 0; i < N; i++) { s += arr[i]; temp[i + 1] = s; } // Initializing DP array with -1 for (int i = 0; i < dp.GetLength(0); i++) { for (int j = 0; j < dp.GetLength(1); j++) { dp[i, j] = -1; } } return maxPoint(0, N - 1, arr, temp); } static public void Main() { // Code long[] arr = { 2, 3, 5 }; int N = arr.Length; // Function call long ans = findMax(arr, N); Console.WriteLine(ans); }}// This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code to implement the approach// dp array to store repeated statevar dp = [];// Function to find the maximum possible pointsfunction maxPoint(i, j, arr, temp) { // Base case if (i >= j) return 0; if (j - i == 1) return 2 * Math.min(arr[i], arr[j]); if (dp[i][j] != -1) return dp[i][j]; var ans = 0; for (var k = i; k < j; k++) { // Points rewarded for left subarray var ans1 = maxPoint(i, k, arr, temp); // Points rewarded for right subarray var ans2 = maxPoint(k + 1, j, arr, temp); var left_element = temp[k + 1] - temp[i]; var right_element = temp[j + 1] - temp[k + 1]; var total = ans1 + ans2 + Math.min(left_element, right_element) * 2; // Total points for partition at current index ans = Math.max(total, ans); } // Store the ans in dp state and return the ans return dp[i][j] = ans;}function findMax(arr, N) { var temp = []; temp.push(0); // To store sum of each elements var s = 0; for (var i = 0; i < N; i++) { s += arr[i]; temp.push(s); } // Initializing DP array with -1 for (var i = 0; i < 100; i++) { dp[i] = []; for (var j = 0; j < 100; j++) { dp[i][j] = -1; } } return maxPoint(0, N - 1, arr, temp);}// Driver Codevar arr = [2, 3, 5];var N = arr.length;// Function callvar ans = findMax(arr, N);console.log(ans);// This code is contributed by Tapesh(tapeshdua420) |
Output
14
Time complexity: O(N2)
Auxiliary space: O(N2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Below is the implementation of the code:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum possible pointsint findMax(vector<long long>& arr, int N){ vector<long long> temp(N+1, 0); // To store sum of each element long long s = 0; for (int i = 0; i < N; i++) { s += arr[i]; temp[i+1] = s; } // Initializing DP array with 0 vector<vector<long long>> dp(N, vector<long long>(N, 0)); // Fill the DP table using tabulation for (int len = 1; len < N; len++) { for (int i = 0; i < N-len; i++) { int j = i + len; if (len == 1) { dp[i][j] = 2 * min(arr[i], arr[j]); } else { for (int k = i; k < j; k++) { long long ans1 = dp[i][k]; long long ans2 = dp[k+1][j]; long long left_element = temp[k+1] - temp[i]; long long right_element = temp[j+1] - temp[k+1]; long long total = ans1 + ans2 + 2 * min(left_element, right_element); // Total points for partition at current index dp[i][j] = max(dp[i][j], total); } } } } // return the answer return dp[0][N-1];}// Driver codeint main() { vector<long long> arr = {2, 3, 5}; int N = arr.size(); // Function call int ans = findMax(arr, N); cout << ans; return 0;} |
Java
import java.util.*;public class MaxPossiblePoints { static int findMax(List<Long> arr, int N) { List<Long> temp = new ArrayList<>(Collections.nCopies(N + 1, 0L)); // To store sum of each element long s = 0; for (int i = 0; i < N; i++) { s += arr.get(i); temp.set(i + 1, s); } // Initializing DP array with 0 long[][] dp = new long[N][N]; // Fill the DP table using tabulation for (int len = 1; len < N; len++) { for (int i = 0; i < N - len; i++) { int j = i + len; if (len == 1) { dp[i][j] = 2 * Math.min(arr.get(i), arr.get(j)); } else { for (int k = i; k < j; k++) { long ans1 = dp[i][k]; long ans2 = dp[k + 1][j]; long leftElement = temp.get(k + 1) - temp.get(i); long rightElement = temp.get(j + 1) - temp.get(k + 1); long total = ans1 + ans2 + 2 * Math.min(leftElement, rightElement); // Total points for partition at the current index dp[i][j] = Math.max(dp[i][j], total); } } } } // Return the answer return (int) dp[0][N - 1]; } public static void main(String[] args) { List<Long> arr = new ArrayList<>(Arrays.asList(2L, 3L, 5L)); int N = arr.size(); // Function call int ans = findMax(arr, N); System.out.println(ans); }}// This code is contributed by Dwaipayan Bandyopadhyay |
Python3
# Function to find the maximum possible pointsdef findMax(arr, N): temp = [0] * (N+1) # To store sum of each element s = 0 for i in range(N): s += arr[i] temp[i+1] = s # Initializing DP array with 0 dp = [[0] * N for _ in range(N)] # Fill the DP table using tabulation for length in range(1, N): for i in range(N-length): j = i + length if length == 1: dp[i][j] = 2 * min(arr[i], arr[j]) else: for k in range(i, j): ans1 = dp[i][k] ans2 = dp[k+1][j] left_element = temp[k+1] - temp[i] right_element = temp[j+1] - temp[k+1] total = ans1 + ans2 + 2 * min(left_element, right_element) # Total points for partition at current index dp[i][j] = max(dp[i][j], total) # Returning result return dp[0][N-1]# Test casearr = [2, 3, 5]N = len(arr)ans = findMax(arr, N)print(ans) |
C#
using System;using System.Collections.Generic;class GFG{ // Function to find the maximum possible points static int findMax(List<long> arr, int N) { List<long> temp = new List<long>(new long[N + 1]); // To store sum of each element long s = 0; for (int i = 0; i < N; i++) { s += arr[i]; temp[i + 1] = s; } // Initializing DP array with 0 long[][] dp = new long[N][]; for (int i = 0; i < N; i++) { dp[i] = new long[N]; for (int j = 0; j < N; j++) { dp[i][j] = 0; } } // Fill the DP table using tabulation for (int len = 1; len < N; len++) { for (int i = 0; i < N - len; i++) { int j = i + len; if (len == 1) { dp[i][j] = 2 * Math.Min(arr[i], arr[j]); } else { for (int k = i; k < j; k++) { long ans1 = dp[i][k]; long ans2 = dp[k + 1][j]; long left_element = temp[k + 1] - temp[i]; long right_element = temp[j + 1] - temp[k + 1]; long total = ans1 + ans2 + 2 * Math.Min(left_element, right_element); // Total points for partition at current index dp[i][j] = Math.Max(dp[i][j], total); } } } } // return the answer return (int)dp[0][N - 1]; } // Driver code static void Main(string[] args) { List<long> arr = new List<long> { 2, 3, 5 }; int N = arr.Count; // Function call int ans = findMax(arr, N); Console.WriteLine(ans); }} |
Javascript
// Function to find the maximum possible pointsfunction findMax(arr, N) { let temp = new Array(N + 1).fill(0); // To store sum of each element let s = 0; for (let i = 0; i < N; i++) { s += arr[i]; temp[i + 1] = s; } // Initializing DP array with 0 let dp = new Array(N); for (let i = 0; i < N; i++) { dp[i] = new Array(N).fill(0); } // Fill the DP table using tabulation for (let len = 1; len < N; len++) { for (let i = 0; i < N - len; i++) { let j = i + len; if (len === 1) { dp[i][j] = 2 * Math.min(arr[i], arr[j]); } else { for (let k = i; k < j; k++) { let ans1 = dp[i][k]; let ans2 = dp[k + 1][j]; let left_element = temp[k + 1] - temp[i]; let right_element = temp[j + 1] - temp[k + 1]; let total = ans1 + ans2 + 2 * Math.min(left_element, right_element); // Total points for partition at current index dp[i][j] = Math.max(dp[i][j], total); } } } } // return the answer return dp[0][N - 1];}// test caselet arr = [2, 3, 5];let N = arr.length;let ans = findMax(arr, N);console.log(ans); |
Output
14
Time complexity: O(N^2)
Auxiliary space: O(N^2)
Related Articles:
