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


  • Approach:

    1. 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.

    2. At the very first thought, it seems to be solvable using a greedy approach by taking the maximum elements from either end.

    3. 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.

    4. Instead of deleting K elements, just think about taking K elements from N given elements to find maximized sum.

    5. 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.

    6. Now, if we will be needing the element from the (n - 1)'th index, we need to delete (K-1)'th element.

    7. Similarly, if we will be needing the element from the (n - 2)'th index, we need to delete (K-2)'th element.

    8. 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.

    9. Return the result.

    10. 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;

}