Given an array of N positive integers. We are allowed to remove element from either of the two ends i.e from the left side or right side of the array. Each time we remove an element, score is increased by value of element * (number of element already removed + 1). The task is to find the maximum score that can be obtained by removing all the element.
Examples:
Input : arr[] = { 1, 3, 1, 5, 2 }.
Output : 43
Remove 1 from left side (score = 1*1 = 1)
then remove 2, score = 1 + 2*2 = 5
then remove 3, score = 5 + 3*3 = 14
then remove 1, score = 14 + 1*4 = 18
then remove 5, score = 18 + 5*5 = 43.
Input : arr[] = { 1, 2 }
Output : 5.
Approach #1
The idea is to use Dynamic Programming. Make a 2D matrix named dp[][] initialized with 0, where dp[i][j] denote the maximum value of score from index from index into index j of the array. So, our final result will be stored in dp[0][n-1].
Now, value for dp[i][j] will be maximum of arr[i] * (number of element already removed + 1) + dp[i+ 1][j] or arr[j] * (number of element already removed + 1) + dp[i][j – 1].
Below is the implementation of this approach:
C++
// CPP program to find maximum score we can get// by removing elements from either end.#include <bits/stdc++.h>#define MAX 50using namespace std;int solve(int dp[][MAX], int a[], int low, int high, int turn){ // If only one element left. if (low == high) return a[low] * turn; // If already calculated, return the value. if (dp[low][high] != 0) return dp[low][high]; // Computing Maximum value when element at // index i and index j is to be choosed. dp[low][high] = max(a[low] * turn + solve(dp, a, low + 1, high, turn + 1), a[high] * turn + solve(dp, a, low, high - 1, turn + 1)); return dp[low][high];}// Driven Programint main(){ int arr[] = { 1, 3, 1, 5, 2 }; int n = sizeof(arr) / sizeof(arr[0]); int dp[MAX][MAX]; memset(dp, 0, sizeof(dp)); cout << solve(dp, arr, 0, n - 1, 1) << endl; return 0;} |
Java
// Java program to find maximum score we can get// by removing elements from either end.public class GFG { static final int MAX = 50; static int solve(int dp[][], int a[], int low, int high, int turn) { // If only one element left. if (low == high) { return a[low] * turn; } // If already calculated, return the value. if (dp[low][high] != 0) { return dp[low][high]; } // Computing Maximum value when element at // index i and index j is to be choosed. dp[low][high] = Math.max(a[low] * turn + solve(dp, a, low + 1, high, turn + 1), a[high] * turn + solve(dp, a, low, high - 1, turn + 1)); return dp[low][high]; }// Driven Program public static void main(String args[]) { int arr[] = {1, 3, 1, 5, 2}; int n = arr.length; int dp[][] = new int[MAX][MAX]; System.out.println(solve(dp, arr, 0, n - 1, 1)); }}/*This code is contributed by 29AjayKumar*/ |
Python 3
# Python 3 program to find maximum# score we can get by removing# elements from either end.MAX = 50def solve(dp, a, low, high, turn): # If only one element left. if (low == high): return a[low] * turn # If already calculated, # return the value. if (dp[low][high] != 0): return dp[low][high] # Computing Maximum value when element # at index i and index j is to be choosed. dp[low][high] = max(a[low] * turn + solve(dp, a, low + 1, high, turn + 1), a[high] * turn + solve(dp, a, low, high - 1, turn + 1)); return dp[low][high]# Driver Codeif __name__ == "__main__": arr = [ 1, 3, 1, 5, 2 ] n = len(arr) dp = [[0 for x in range(MAX)] for y in range(MAX)] print(solve(dp, arr, 0, n - 1, 1))# This code is contributed by ChitraNayal |
C#
// C# program to find maximum score we can get // by removing elements from either end. using System; class GFG { static int MAX = 50; static int solve(int[,] dp, int[] a, int low, int high, int turn) { // If only one element left. if (low == high) return a[low] * turn; // If already calculated, return the value. if (dp[low, high] != 0) return dp[low, high]; // Computing Maximum value when element at // index i and index j is to be choosed. dp[low,high] = Math.Max(a[low] * turn + solve(dp, a, low + 1, high, turn + 1), a[high] * turn + solve(dp, a, low, high - 1, turn + 1)); return dp[low, high]; } // Driven code static void Main() { int[] arr = new int[]{ 1, 3, 1, 5, 2 }; int n = arr.Length; int[,] dp = new int[MAX,MAX]; for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) dp[i, j] = 0; Console.Write(solve(dp, arr, 0, n - 1, 1)); }}// This code is contributed by DrRoot_ |
PHP
<?php// PHP program to find maximum score we can // get by removing elements from either end. $MAX = 50 ;function solve($dp, $a, $low, $high, $turn) { // If only one element left. if ($low == $high) return $a[$low] * $turn; // If already calculated, return the value. if ($dp[$low][$high] != 0) return $dp[$low][$high]; // Computing Maximum value when element at // index i and index j is to be choosed. $dp[$low][$high] = max($a[$low] * $turn + solve($dp, $a, $low + 1, $high, $turn + 1), $a[$high] * $turn + solve($dp, $a, $low, $high - 1, $turn + 1)); return $dp[$low][$high]; } // Driver Code$arr = array(1, 3, 1, 5, 2 ) ; $n = count($arr) ;$dp = array() ;for($i = 0; $i < $MAX ; $i++){ $dp[$i] = array_fill($i, $MAX, 0) ;}echo solve($dp, $arr, 0, $n - 1, 1); // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript program to find maximum score we can get// by removing elements from either end.let MAX = 50; function solve(dp, a, low, high, turn) { // If only one element left. if (low == high) { return Math.floor(a[low] * turn); } // If already calculated, return the value. if (dp[low][high] != 0) { return dp[low][high]; } // Computing Maximum value when element at // index i and index j is to be choosed. dp[low][high] = Math.max(Math.floor(a[low] * turn )+ solve(dp, a, low + 1, high, turn + 1), Math.floor(a[high] * turn) + solve(dp, a, low, high - 1, turn + 1)); return dp[low][high]; } // driver function let arr = [1, 3, 1, 5, 2]; let n = arr.length; let dp = new Array(MAX); // Loop to create 2D array using 1D array for (var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for (var i = 0; i < dp.length; i++) { for (var j = 0; j < dp.length; j++) { dp[i][j] = 0; } } document.write(solve(dp, arr, 0, n - 1, 1)); // This code is contributed by susmitakundugoaldanga.</script> |
Output
43
Approach #2
Apart from DP, a more intuitive solution will be a Greedy approach, where we choose the optimal solution at each step going forward. An optimal step will be to keep larger element inside as long as possible so that it can have a higher multiplier and higher sum:
C++
#include <iostream>using namespace std;int main() { int stk[] = { 1, 3, 1, 5, 2 }; int removed = 0; int top = 0; int sum = 0; int bottom = sizeof(stk) / sizeof(int) - 1; while (removed < sizeof(stk) / sizeof(int)) { // checking for the smaller element and considering that as popped. if (stk[top] <= stk[bottom]) { sum += stk[top] * (removed + 1); top += 1; } else { sum += stk[bottom] * (removed + 1); bottom -= 1; } removed += 1; } cout << sum << endl;}// This code is contributed by aadityaburujwale. |
Python
stk = [1, 3, 1, 5, 2]removed = 0top = 0sum = 0bottom = len(stk)-1while removed < len(stk): # checking for the smaller element and considering that as popped. if stk[top] <= stk[bottom]: sum += stk[top]*(removed+1) top += 1 else: sum += stk[bottom]*(removed+1) bottom -= 1 removed += 1print(sum)# Code contributed by Sanyam Jain |
Java
// Java program for the above approachimport java.io.*;class GFG { public static void main(String[] args) { int[] stk = { 1, 3, 1, 5, 2 }; int removed = 0; int top = 0; int sum = 0; int bottom = stk.length - 1; while (removed < stk.length) { // checking for the smaller element and considering that as popped. if (stk[top] <= stk[bottom]) { sum += stk[top] * (removed + 1); top += 1; } else { sum += stk[bottom] * (removed + 1); bottom -= 1; } removed += 1; } System.out.print(sum); }}// This code is contributed by lokeshmvs21. |
C#
// C# program for the above approachusing System;public class GFG { static public void Main() { // Code int[] stk = { 1, 3, 1, 5, 2 }; int removed = 0; int top = 0; int sum = 0; int bottom = stk.Length - 1; while (removed < stk.Length) { // checking for the smaller element and // considering that as popped. if (stk[top] <= stk[bottom]) { sum += stk[top] * (removed + 1); top += 1; } else { sum += stk[bottom] * (removed + 1); bottom -= 1; } removed += 1; } Console.Write(sum); }}// This code is contributed by lokeshmvs21. |
Javascript
function solve(stk){ let removed = 0; let top = 0; let sum = 0; let x= stk.length; let bottom = x - 1; while (removed < x) { // checking for the smaller element and considering that as popped. if (stk[top] <= stk[bottom]) { sum += stk[top] * (removed + 1); top += 1; } else { sum += stk[bottom] * (removed + 1); bottom -= 1; } removed += 1; } console.log(sum);}// driver code let stk = [ 1, 3, 1, 5, 2 ]; solve(stk);// This code is contributed by garg28harsh. |
Output
43
Time Complexity : O(n)
Space Complexity : O(1)
This article is contributed by Anuj Chauhan. 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!
