hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Maximize Score
Problem: Maximize Score
Problem Link: https://www.codingninjas.com/codestudio/problems/maximize-score_1229509
Company Asked: Google
Approach:
Since we need to take the elements either from the left or from the right and we need to maximize the score, we need to choose the elements in such a way that it returns maximized results.
At the very first thought, it seems to be solvable using a greedy approach by taking the maximum elements from either end.
But if we think a bit about which one to choose between two equal elements on either side, then we came to know that mentioned greedy solution will not work much to have a maximized answer.
Instead of deleting K elements, just think about taking K elements from N given elements to find maximized sum.
Let's say we are said to take K elements from the 0 index, then we will be taking 0 to (K-1)'th elements.
Now, if we will be needing the element from the (n - 1)'th index, we need to delete (K-1)'th element.
Similarly, if we will be needing the element from the (n - 2)'th index, we need to delete (K-2)'th element.
If we do the same for K times, we will be having the sum of K elements. We need to take the maximum of those sums.
Return the result.
For steps 5, 6, and 7 what I did -
Took a vector newVector.
Insert K elements from the back of the given array within the newVector.
Then insert K elements of the given array starting from 0 index.
The size of the newVector will be 2K.
For index 0, 1, 2, ..... K, take the sum of K elements and calculate the maximum among them.
Returned the maximum value.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(N)
Code [C++]
#include <bits/stdc++.h>
int maximizeScore(vector<int> &arr, int n, int k)
{
vector<int>modifiedArray;
int tempK = 0;
for(int i=n-1; tempK<k && i>=0; i--){
modifiedArray.push_back(arr[i]);
tempK++;
}
reverse(modifiedArray.begin(), modifiedArray.end());
tempK = 0;
for(int i=0; tempK<k && i<n; i++){
modifiedArray.push_back(arr[i]);
tempK++;
}
int left = 0, right = 0;
n = modifiedArray.size();
int sum = 0, maxSum = 0;
while(right < n){
if((right - left) == k){
maxSum = max(maxSum, sum);
sum -= modifiedArray[left++];
}
sum += modifiedArray[right];
right++;
}
maxSum = max(maxSum, sum);
return maxSum;
}