Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach
3.1.
Brute force Approach
3.2.
Efficient Approach
3.3.
Algorithm
3.4.
Program
3.4.1.
Input
3.4.2.
Output
3.4.3.
Time Complexity
3.4.4.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is Dynamic Programming?
4.2.
What is an array?
4.3.
What distinguishes dynamic programming from memoization and recursion?
4.4.
What are the cons of memoization or a top-down approach?
4.5.
Are there any other Data Structures and Algorithms content in Coding Ninjas Studio?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Maximize the sum of the product of neighboring elements of the element removed from Array

Author Ujjawal Gupta
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Recently, Ninja has changed his college. His new programming teacher is curious to know where ninja stands in programming, so she has given a problem in which ninjas have an array of size ‘N’. His task is to find the maximum sum of the product of neighboring elements of the element removed from the array. Your task is to help him to solve this problem.

The above problem is the standard Dynamic Programming problem. Dynamic programming based-coding problems are widely asked in various coding contests and various coding interviews.

max sum

In this blog, we will solve the above problem using dynamic programming.

Problem Statement

You are given an array ‘ARR’ of size ‘N ’. Your task is to reduce the size of an array to 2 by performing exactly ‘N-2’ operations; in each operation, you get some score as:

  • Choose any index ‘i’ between 1<= ‘i’ <= ‘N-1’.
  • Delete the ith element from the array ‘ARR’.
  • Add ‘ARR[i+1]’ *  ‘ARR[i-1]’ in the score.
     

Note: In each operation, the size of an array is reduced by 1.

Example

Let ‘ARR’={3,5,4,1}. If we delete five and after that 4, our score is 4*3+3*1=15, the maximum possible score for this array.  

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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 stockMaximum profitLongest Common prefixwildcard 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!

Previous article
Maximize the Sum of Elements ARR[i] Selected by Jumping Index by Value i
Next article
Longest Palindromic Substring
Live masterclass