Algorithm/DS Problem#6: HackerRank: The Maximum Subarray + Maximum Subsequence sum

We define subsequence as any subset of an array. We define a subarray as a contiguous subsequence in an array.

Given an array, find the maximum possible sum among:

1. all nonempty subarrays.
2. all nonempty subsequences.

Print the two values as space-separated integers on one line.

Note that empty subarrays/subsequences should not be considered.

Example

The maximum subarray sum is comprised of elements at inidices . Their sum is . The maximum subsequence sum is comprised of elements at indices and their sum is .

Function Description

Complete the maxSubarray function in the editor below.

maxSubarray has the following parameter(s):

• int arr[n]: an array of integers

Returns

• int[2]: the maximum subarray and subsequence sums

Input Format

The first line of input contains a single integer , the number of test cases.

The first line of each test case contains a single integer .
The second line contains space-separated integers where .

Constraints

The subarray and subsequences you consider should have at least one element.

Sample Input

2
4
1 2 3 4
6
2 -1 2 3 4 -5

Sample Output

10 10
10 11

Explanation

In the first case: The maximum sum for both types of subsequences is just the sum of all the elements since they are all positive.

In the second case: The subarray is the subarray with the maximum sum, and is the subsequence with the maximum sum.

Solution

The problem statement is actually a bundle of two different algorithm problems — Maximum subarray sum + Maximum subsequence sum.

I am not going to explain about solving maximum subarray sum using famous Kadane’s algorithm using dynamic programming approach. You can refer to plenty of resources on the net. Now lets see how we can use the same for loop to find both maximum sequence sum and max subarray sum.

The problem asks for array sequence and no constraint is there whether they need to be non-adjacent only. So elements involved in creating maximum possible sum can be either :
(a) elements of contiguous sub array
OR
(b) elements with both contiguous and non-contiguous sub array

Lets look at an example: