Company: IBM
Difficulty: medium
Max Beauty For an array of integers, arr[n] , its prefix sum array, psum[n] , is constructed as psum[i] = sum(arr[0]...arr[i]) where 0≤ i . The beauty of psum[n] is psum[0] - psum[1] + psum[2] - psum[3] + ... (-1) n-1 psum[n-1] . Note: (-1) n-1 psum[n-1] indicates the last element may be added or subtracted, depending on the parity of n-1. If arr can be rearranged arbitrarily, find the maximum possible value of the beauty of psum[n] . Example n = 5 arr = [3, 4, 5, 1, 1] The optimal arrangement of arr is [3, 1, 5, 1, 4]. psum = [3, 4, 9, 10, 14] The beauty of psum is 3 - 4 + 9 - 10 + 14 = 12. The answer is 12. Note that there can be multiple optimal arrangements like [5, 1, 3, 1, 4], [4, 1, 3, 1, 4]. Function Description Complete the function getMaxBeauty in the editor below. getMaxBeauty has the following parameter: int arr[n] : an array of integers Returns long int : the maximum possible beauty of psum Constraints 1 ≤ n ≤ 10 5 1 ≤ arr[i] ≤ 10 9 Sample Test Cases Sample Case 0 4 4 1 2