Company: Publicis sapients SDE role
Difficulty: medium
Maximum Beauty Problem Description Choose k non-empty disjoint subarrays from an array arr of n integers. Let sub_sum[i] denote the sum of elements in the i th subarray. The beauty of arr is 1 * sub_sum[1] + 2 * sub_sum[2] + ... + k * sub_sum[k] . In other words, beauty = summation(i * sub_sum[i]) for 1 . Given arr and k , find the maximum possible beauty of the array. If it is not possible to choose k non-empty disjoint subarrays, return -1. Note: A subarray is a contiguous subsegment of an array. It is not necessary to include every element in a subarray. The chosen subarrays must be disjoint, i.e., no two subarrays may contain any common index. The order of chosen subarrays cannot be changed. If i , then the last index of the i th subarray must be less than the first index of the j th subarray for each possible pair (i, j) . The function is expected to return a long int . The function accepts the following parameters: int k : the number of disjoint subarrays to choose int arr[n] : a