[Solution] Maximum Subarray solution codechef

Maximum Subarray solution codechef – Given two arrays A and B of sizes N and M respectively. You can apply the following operation until the array B is non-empty:

Table of Contents

[Solution] Maximum Subarray solution codechef

  • Choose either the first or the last element of array B.
  • Insert the chosen element to either the front or the back of array A.
  • Delete the chosen element from array B.

For example, let A = [9, 7] and B = [1, 3, 2]. In one operation, we can choose either X = 1 or X = 2 (first or last element of array B). We can insert X in array A and make it either A = [X, 9, 7] or A = [9, 7, X]. The chosen X is deleted from array B. Thus, it will become either B = [3, 2] (when chosen X is 1) or B = [1, 3] (when chosen X is 2).

Find the maximum sum of any subarray of the array A that you can achieve after performing exactly M operations.

Note: A subarray of an array is formed by deleting some (possibly zero) elements from the beginning of the array and some (possible zero) elements from the end of the array.

[Solution] Maximum Subarray solution codechef

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of 4 lines of input.
    • The first line of each test contains a single integer N, the size of array A.
    • The next line contains N space-separated integers, denoting elements of array A.
    • The third line of each test contains a single integer M, the size of array B.
    • The next line contains M space-separated integers, denoting elements of array B.

Output Format

For each test case, output on a new line the maximum sum of any subarray of the array A that you can achieve after performing exactly M operations.

Constraints

  • 1 \leq T \leq 10
  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • -10^8 \leq A_i, B_i \leq 10^8

[Solution] Maximum Subarray solution codechef

Input

Output

3
5
3 26 -79 72 23
2
66 44
1
81
1
-97
5
10 -5 14 -20 4
3
-10 5 -2
205
81
24

[Solution] Maximum Subarray solution codechef Explanation:

Test case 1:

  • Operation 1: Add the first element of array B to the back of array A. Thus, A = [3, 26, -79, 72, 23, 66] and B = [44].
  • Operation 2: Add the first element of array B to the back of array A. Thus, A = [3, 26, -79, 72, 23, 66, 44] and B = [].

The, maximum sum subarray of array A is [72, 23, 66, 44] having sum 72+23+66+44=205.

Test case 2:

  • Operation 1: Add the first element of array B to the front of array A. Thus, A = [-97, 81] and B = [].

The, maximum sum subarray of array A is [81] having sum 81.

Test case 3:

  • Operation 1: Add the last element of array B to the back of array A. Thus, A = [10, -5, 14, -20, 4, -2] and B = [-10, 5].
  • Operation 2: Add the last element of array B to the front of array A. Thus, A = [5, 10, -5, 14, -20, 4, -2] and B = [-10].
  • Operation 3: Add the first element of array B to the front of array A. Thus, A = [-10, 5, 10, -5, 14, -20, 4, -2] and B = [].

The, maximum sum subarray of array A is [5, 10, -5, 14] having sum 5+10-5+14 = 24.

For Solution

“Click Here”

Leave a Comment