SDE - 1

You are given an array 'arr' of 'n' integers.

You have to divide the array into some subarrays such that each element is present in exactly one of the subarrays.

The length of each subarray should be at most 'k'. After partitioning all the elements of each subarray will be changed to the maximum element present in that subarray.

Find the maximum possible sum of all the elements after partitioning.

Note:

Input is given such that the answer will fit in a 32-bit integer.

Example:

Input: 'k' = 3, 'arr' = [1, 20, 13, 4, 4, 1]

Output: 80

Explanation:
We can divide the array into the following subarrays
[1,20] max of this subarray is 20 so the contribution of 
this subarray in the final answer will be 20*2=40.
[13,4,4]  max of this subarray is 13 so the contribution of 
this subarray in the final answer will be 13*3=39.
[1]  max of this subarray is 1 so the contribution of this 
subarray in the final answer will be 1*1=1.

So, the answer will be 40 + 39 + 1 = 80.

Given an array/list of integers of length ‘N’, there is a sliding window of size ‘K’ which moves from the beginning of the array, to the very end. You can only see the ‘K’ numbers in a particular window at a time. For each of the 'N'-'K'+1 different windows thus formed, you are supposed to return the maximum element in each of them, from the given array/list.

Given two strings, ‘A’ and ‘B’. Return the shortest supersequence string ‘S’, containing both ‘A’ and ‘B’ as its subsequences. If there are multiple answers, return any of them.

Note: A string 's' is a subsequence of string 't' if deleting some number of characters from 't' (possibly 0) results in the string 's'.

For example:

Suppose ‘A’ = “brute”, and ‘B’ = “groot”

The shortest supersequence will be “bgruoote”. As shown below, it contains both ‘A’ and ‘B’ as subsequences.

A   A A     A A
b g r u o o t e
  B B   B B B  

It can be proved that the length of supersequence for this input cannot be less than 8. So the output will be bgruoote.