FastPrep
Problem · Array

Maximize Sum of Two Non-Overlapping Fragments

Learn this problem
● HardMicrosoftNEW GRADOA
See Microsoft hiring insights

Problem statement

There is an array A of N integers which may contain positive and negative values. Choose two fragments, one of length K and one of length L, to maximize the sum of the elements that belong to the chosen fragments. However, if any individual element belongs to both fragments at the same time, each such element is added to the final sum only once and with a changed sign (i.e., negative values become positive values, and vice versa).

Write a function:

def solution(A, K, L)

that, given an array A of N integers and integers K and L, returns the maximum total sum that can be obtained.

Function

microsoftMaximizeSum(A: int[], K: int, L: int) → int

Examples

Example 1

A = [1, 3, -4, 2, -1]K = 3L = 2return = 10

For A = [1, 3, -4, 2, -1], K = 3, L = 2, you can choose fragment [1, 3, -4] and fragment [-4, 2]. The third element of A belongs to both fragments, so the function should return 1 + 3 + -(-4) + 2 = 10.

Example 2

A = [-5, -3, -4]K = 1L = 3return = -2

For A = [-5, -3, -4], K = 1, L = 3, the segment of length L will contain each element of A. Then choosing -5 as the only element of the K segment will change its sign in the final sum. The function should return -2.

More Microsoft problems

drafts saved locally
public int microsoftMaximizeSum(int[] A, int K, int L) {
  // write your code here :)

}
A[1, 3, -4, 2, -1]
K3
L2
expected10
checking account