Stone Game V

Brute Force Approach⚡

Let's first start with the Brute force approach to solve this problem.

The brute force approach would be to create all the possible scenarios, i.e., we have to break to row in every possible way, then call the recursive function and store its answer. Now out of all the answers, we will check which one’s greater as we have to print the answer with maximum value. We are leaving the coding part to you as we will discuss the major approach to this question, i.e., dynamic programming.

Dynamic Programming Approach🎯

The intuition is very straightforward. We have to take the help of Dynamic Programming here. 

But how?

We will create a DP table and DP[i][j] will represent the max score you can obtain from stones in ‘i’ to ‘j’.

We will also create a prefix sum table where SUM[i][j] will store the sum of ARR[i. . .j].

Now our approach will be simple we will create all possible scenarios: 

For that we will use a variable ‘k’ which will go from i to j - 1, then we will have two choices for score, i.e., either SUM[i][k] + DP[i][k] or SUM[k + 1][j] + DP[k + 1][j] (left half or right half).

Now let’s see the above words in action.

Code

#include <iostream>
#include <vector>
using namespace std;

int stones(vector<int> &arr)
{
   int n = arr.size();

   // Prefix Array.
   vector<int> sum(n + 1, 0);
   for (int i = 1; i <= n; i++)
   {
       sum[i] = sum[i - 1] + arr[i - 1];
   }

   // DP array.
   vector<vector<int> > dp(n, vector<int>(n, 0));

   for (int l = 1; l < n; l++)
   {
       for (int i = 0; i < n - l; i++)
       {
           int j = i + l, res = 0;
           for (int k = i; k < j; k++)
           {
               // Sum of two parts namely left and right.
               int left = sum[k + 1] - sum[i], right = sum[j + 1] - sum[k + 1];

               // If the sum of the left part is less than that of the right part.
               if (left < right)
               {
                   res = max(res, left + dp[i][k]);
               }
               else if (left > right)
               {
                   res = max(res, right + dp[k + 1][j]);
               }

               // If it's equal.
               else
               {
                   res = max(res, left + dp[i][k]);
                   res = max(res, right + dp[k + 1][j]);
               }
           }

           // Storing the answer in the 'DP' table.
           dp[i][j] = res;
       }
   }

   // Return the answer.
   return dp[0][n - 1];
}

int main()
{
   int n;
   cin >> n;

   // Taking Input.
   vector<int> arr(n, 0);
   for (int i = 0; i < n; i++)
   {
       int x;
       cin >> x;
       arr[i] = x;
   }

   cout << stones(arr);
  
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

6
1 2 3 4 5 6

Output

14

Time Complexity⌚

O(N^3), where ‘N’ is the length of the array.
Reason: As we are using three nested loops, thus time complexity comes to N^3.

Space Complexity🔥

O(N ^ 2), where ‘N’ is the length of the array.
Reason: Since we are using a ‘DP’ array of size N ^ 2.

Check out Longest Common Substring

Optimized Approach💥

Now, if we look closely as ‘k’ goes from ‘i’ to ‘j.’ The sum of the left part, i.e., SUM[i][k], increases continuously, and it remains a valid subarray for our consideration for calculating DP[i][j] till the point when it becomes greater than the right half. Now from that point, all the right ones can also be taken into consideration. Basically, we can say that this is a critical point ‘kC’. Now, a binary search can be used to find this critical point. Thus we will have two conclusions.

DP[i][j] = max([max(SUM[i][k] + DP[i][k]) for k: i to k], [max(sum[k][j] + DP[k][j]) for k: k'+1 to j] )

Now if we start calculating these above by iterating ‘k’ from i to ‘kC’, it will again costs us O(N) time then we will be back to our first solution. Instead of this what we can do is to maintain 2 more arrays, lets say, LEFT and RIGHT defined as:

LEFT[i][j] = max( SUM[i][k] + DP[i][k] for k: i to j )

RIGHT[i][j] = max( SUM[k][j] + DP[k][j] for k: i to j )

And then we can redefine

DP[i][j] = max( LEFT[i][k], RIGHT[k+1][j] )

Also while calculating the DP table we can also calculate the LEFT and RIGHT arrays in the following way.

LEFT[i][j] = max( LEFT[i][j-1], SUM[i][j] + DP[i][j] )

RIGHT[i][j] = max( RIGHT[i+1][j], SUM[i][j] + DP[i][j] )

It might get a little confusing here but as we will see the code all things will become clear.

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function for performing Binary Search.
int search(vector<int> &pre, int l, int r)
{
   int sum = pre[r + 1] - pre[l], L = l;
   while (l < r)
   {
       int m = l + ((r - l) >> 1);
       if (((pre[m + 1] - pre[L]) << 1) >= sum)
       {
           r = m;
       }
       else
       {
           l = m + 1;
       }
   }

   return l;
}

// Function that will return our final answer.
int stones(vector<int> &stoneValue)
{
   int n = stoneValue.size();
   vector<int> pre(n + 1, 0);

   // Initializing prefix array.
   for (int i = 1; i <= n; i++)
   {
       pre[i] = pre[i - 1] + stoneValue[i - 1];
   }

   // Declaring DP array.
   vector<vector<int> > dp(n, vector<int>(n, 0));
   vector<vector<int> > left(n, vector<int>(n, 0));
   vector<vector<int> > right(n, vector<int>(n, 0));

   for (int i = 0; i < n; i++)
   {
       left[i][i] = right[i][i] = stoneValue[i];
   }

   for (int l = 1; l < n; l++)
   {
       for (int i = 0; i < n - l; i++)
       {
           // Performing Binary search
           int j = i + l, k = search(pre, i, j);
           int sum = pre[j + 1] - pre[i], leftHalf = pre[k + 1] - pre[i];
           if ((leftHalf << 1) == sum)
           {
               dp[i][j] = max(left[i][k], right[k + 1][j]);
           }
           else
           {
               dp[i][j] = max(k == i ? 0 : left[i][k - 1], k == j ? 0 : right[k + 1][j]);
           }

           left[i][j] = max(left[i][j - 1], sum + dp[i][j]);
           right[i][j] = max(right[i + 1][j], sum + dp[i][j]);
       }
   }

   // Returning the answer.
   return dp[0][n - 1];
}

int main()
{
   int n;
   cin >> n;

   // Taking Input.
   vector<int> arr(n, 0);
   for (int i = 0; i < n; i++)
   {
       int x;
       cin >> x;
       arr[i] = x;
   }

   // Calling the function.
   cout << stones(arr);
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input🧾

6
1 2 3 4 5 6

Output

14

Time Complexity⌚

O((N ^ 2) * (logN)), where ‘N’ is the length of the array.
Reason: As we are using looping over the ‘DP’ table, it will cost us O(N ^ 2). Also while iterating, we are performing a binary search which will cost us O(log(N)) time. Thus, the overall time complexity is O((N ^ 2) * log(N)).

Space Complexity🔥

O(N ^ 2), where ‘N’ is the length of the array.
Reason: Since we are using a ‘DP’ array of size N ^ N.

Check out this problem - Minimum Coin Change Problem 

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

Now you have understood how to solve the problem, stone game V. We saw how we could apply binary search and DP together and drastically reduce the time complexity. DP and Binary Search both are vast topics to explore, but you don’t have to worry about any of it when your ninja friend is here. So head over to our practice platform Coding Ninjas Studio to practice top problems and many more. 

Till then, Happy Coding!