Zensar Technologies OA 2024 Partition Array for Maximum Sum | Dynamic Programming

Problem Statement Given an integer array arr and an integer k, partition the array into one or more contiguous subarrays such that: Each subarray has a length of at most k. After partitioning, every element in a subarray becomes equal to the maximum element of that subarray. Return the largest possible sum of the array after partitioning. Example 1 Input arr = [1,15,7,9,2,5,10] k = 3 Output 84 Explanation One optimal partition is: [1,15,7] [9] [2,5,10] After replacing each partition ...