Company: Publicis Sapient_8oct
Difficulty: medium
Maximum Beauty of an Array 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] + 3 * sub_sum[3] + ... + 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) . Examples Example 1: Input: n = 5, arr = [1, 3, -1, -2, 1], k = 4 Output: 8 Explanation: Choose the k subarrays as follows ( arr[l