Approach
Brute force Approach
The naive approach of the above problem is to generate all the possible combinations of selecting index ‘I’, find the score from each, and print the maximum among them.
However, this is not an efficient approach as generating all the possible combinations takes O(n^n) time complexity.
Efficient Approach
The above problem can also be solved using dynamic programming. The idea is to create an array ‘DP[][]’, in which ‘DP[I][J]’ is the maximum score for subarray ‘I’ to ‘J’, which can be concluded as ‘ARR[I]’ * ‘ARR[j]’+ maximum score in subarray ‘I+1’ to ‘J-1’. The algorithm is as follows:
Algorithm
-
Define the function ‘maximumScore()’, which takes array ‘ARR’ as a parameter and returns the final answer.
-
Create 2-dimensional ‘DP[][]’ array.
-
Iterate loop from ‘DIFF’=1 to ‘DIFF’ < ’ ARR.SIZE()’.
-
Iterate another loop from ‘I’=0 to ‘I’<’ N’.
- Create variable ‘J’ = ‘I’+ ‘DIFF’.
- ‘DP[I][J]’=0.
-
Iterate loop from ‘IT’=’I+1’ to ‘J’ and update the value of ‘DP[I][J]’ in each iteration.
-
Return ‘DP[0][ARR.SIZE()]’.
- Call the maximumScore() function inside the main function.
Program
#include <iostream>
#include <vector>
using namespace std;
/*
Function for getting the answer.
*/
int maximumScore(vector<int> &arr)
{
/*
Creating 2-d dp array to store the result.
*/
int dp[arr.size()][arr.size()];
for (int diff = 1; diff < arr.size(); diff++)
{
for (int i = 0; diff + i < arr.size(); i++)
{
int j = i + diff;
/*
Initially initialize dp[i][j]=0.
*/
dp[i][j] = 0;
for (int it = i + 1; it < j; it++)
{
/*
Update the value of dp[i][j].
*/
dp[i][j] = max(dp[i][j], arr[i] * arr[j] + dp[i][it] + dp[it][j]);
}
}
}
return dp[0][arr.size() - 1];
}
int main()
{
/*
Taking number of elements in the array as an input.
*/
int n;
cin >> n;
/*
Taking array as an input.
*/
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
/*
Call function
*/
int ans = maximumScore(arr);
/*
Print the final answer.
*/
cout << ans;
return 0;
}
You can also try this code with Online C++ Compiler
Input
4
3 5 4 1
Output
15
Time Complexity
Here, one loop runs inside another. That’s why the time complexity of the above code is O(N^3).
Space Complexity
Creating a 2-dimensional array takes O(N^2).
Check out Longest Common Substring
Frequently Asked Questions
What is Dynamic Programming?
Dynamic programming is a problem-solving technique that divides problems into sub-problems and saves the result for later use, eliminating the need to recalculate the result. The optimal substructure property describes how subproblems are optimized to improve the overall solution.
What is an array?
An array data structure, or simply an array, is a data structure in computer science that consists of a collection of elements, each of which is identified by at least one array index or key. An array is stored in such a way that the position of each element can be calculated using a mathematical formula from its index tuple.
What distinguishes dynamic programming from memoization and recursion?
Recursion is the process of repeatedly calling the same function. Memorization is a method of storing the answers to subproblems that have been solved. Dynamic programming is a method of recursive problem solving that involves storing the solutions to previously solved subproblems.
What are the cons of memoization or a top-down approach?
It uses the recursion technique that occupies more memory in the call stack. Sometimes when the recursion is too deep, the stack overflow condition will occur. It occupies more memory which degrades the overall performance.
Are there any other Data Structures and Algorithms content in Coding Ninjas Studio?
Yes, Coding Ninjas Studio allows you to practice coding as well as answer frequently asked interview questions. The more we practice, the more likely we are to acquire a job at our dream company.
Conclusion
In this blog, we have learned how to maximize the sum of the product of neighboring elements of the element removed from array using Dynamic programming. I suggest you solve more problems based on this. These are the Best time to buy and sell a stock, Maximum profit, Longest Common prefix, wildcard pattern matching, and rod cutting problem.
Hence learning never stops, and there is a lot more to learn.
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!
19+ registered 
