Maximum Sum of K Non-Overlapping Fixed-Length Subarrays

Problem Statement

Maximum Sum of K Non-Overlapping Fixed-Length Subarrays You are given an array A of N integers, and three integers K, L, and M . You must select exactly K pairwise non-overlapping contiguous subarrays from A. Each selected subarray must have a length of exactly L. For each selected subarray, you must evaluate its score using exactly one of the following two methods: Standard Sum : The sum of all elements in the subarray. Alternating Sum : The sum of the elements in the subarray with strictly alternating signs , starting with a positive sign. For a subarray starting at index i , this evaluates to A[i] - A[i+1] + A[i+2] - ... + (-1)^(L-1) * A[i+L-1] . You are permitted to use the Alternating Sum evaluation method for at most M of your K selected subarrays. The remaining chosen subarrays must use the Standard Sum method. Find the maximum possible total score achievable by optimally selecting the subarrays and their evaluation methods. Input Format The first line contains a integer, N, den