A book publisher collected data on the readability level of his n books. Book publisher can print any book in 1 unit of time. Readability-Coefficient of a book is defined as the time taken to print that book including previous books multiplied by its readability level, i.e. total_time * readability[i], the task is to return the maximum sum of Readability-Coefficient that the publisher can obtain after books are printed, you can keep the books even if its readability level is negative, so as to get the maximum value of total Readability-Coefficient. Books can be printed in any order and the publisher can discard some books to get this maximum value.
Examples:
Input: readability: [-1, -7, 3]
Output: 5
Explanation: Here we could have taken -1 and -7 but taking both of them reduces the total Readability-Coefficient , as -7*1 + -1*2 + 3*3 = 0 , we can neglect -7 readability and -1 readability but now the total Readability-Coefficient becomes 3*1 = 3, hence we keep -1*1 + 3*2 = 5 as the total Readability-Coefficient, which is the maximum value.Input: readability: [-1, -3, -9]
Output: 0
Explanation: People do not like the books. No book is published.
Approach: To solve the problem follow the below idea:
The idea behind this is to Take or Not Take the current Book with certain readability, and simultaneously keep incrementing the counter to keep track of the time.
Steps to solve the problem:
- The solver function is designed to recursively explore the possibilities and calculate the maximum readability.
- It takes three parameters: readability (vector of integers), i (current index), and counter (a counter to keep track of the time).
- Base Cases:
- If i exceeds the size of the readability vector, it returns 0, as there are no more elements to consider.
- If the value for the current i and counter combination has already been calculated (dp[i][counter] is not -1), it returns the memoized result.
- Recursive Cases:
- It considers two possibilities: either taking the current readability or not taking it.
- take is calculated by multiplying the readability at index i with the counter and recursively calling solver for the next index (i+1) and an incremented counter (counter+1).
- nottake is calculated by directly calling solver for the next index (i+1) with the same counter.
- Sorting:
- The readability vector is sorted before the process starts.
- Modulo Operation:The final result is taken modulo 1000000007 to ensure that the result remains within the desired range.
Below is the implementation of the above approach:
C++14
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Global 2D array for memoizationint dp[1001][1001];// Recursive function to find maximum readabilityint solver(vector<int>& readability, int i, int counter){ // Base case: If index exceeds the // size of 'readability' if (i >= readability.size()) { return 0; } // If the result for current 'i' and 'counter' // combination is already calculated if (dp[i][counter] != -1) return dp[i][counter]; // Calculate 'take' and 'nottake' // options recursively int take = readability[i] * counter + solver(readability, i + 1, counter + 1); int nottake = solver(readability, i + 1, counter); // Store the result in 'dp' array and return // the maximum value return dp[i][counter] = max(take, nottake) % 1000000007;}// Function to find maximum readabilityint maxreadability(vector<int>& readability){ // Sort the 'readability' vector sort(readability.begin(), readability.end()); // Initialize 'dp' array with -1 // for memoization memset(dp, -1, sizeof(dp)); // Start the recursion from index 0 // with counter 1 return solver(readability, 0, 1);}// Drivers codeint main(){ // Example 'readability' vector vector<int> readability = { -1, -7, -3, 5, -9 }; // Call the 'maxreadability' function and // print the result cout << maxreadability(readability); return 0;} |
10
Time Complexity: O(n^2). where n is the size of the ‘readability‘ vector
Auxiliary Space: O(n^2) .
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
