finding maximum Subarray without Repetition

Contributed by Anurag Gupta,

I got this question while giving Hiring test for Microsoft,
The question is very simple,

we are given an array with positive numbers, we have to find Subarray with maximum sum with unique elements.

This is a variation of Classical Larget Subarray sum problem ( Kadane’s Algorithm ) , shown below.

Input

first line of input takes number of elements in the array let say n,
second line contains n elements , each representing one element of array.

Output

first line of output prints ans i.e. subarray with maximum sum
second line contains the sum of subarray printed above.

# test case 1                            #Output
5                                         subarray: 2 3 1 5
1 2 3 1 5                                 max_sum:11
#test case 2                             #Output
6                                         subarray:3 5 2
1 2 3 3 5 2                               max_sum:10
#test case 3                             #Output
4                                         subarray:5
5 5 5 4                                  max_sum:5

Approaches

There may be couple of approaches to solve that problem,
first might be the brute force approach which could be implemented in O(n³) .

Bruteforce Approach
we generate all possible O(n²) subarrays and then we choose the one having maximum sum out of those having unique elements which will cost O(n) giving us O(n³) solution.

Using Kadane’s Algorithm
Kadane’s algorithm can be modified and used in this example which lets us solve that problem in O(n²).
Kadane’s algorithm wiki GeeksforGeeks

We can start from empty subarray as answer start including one element until any duplicate element comes in that array which will take O(n), for finding if this has already came or not be will have to go through start to end of currently selected subsubarray with no duplicate members.

we will check if this subarray has max sum or not and store in final_start and final_end which has sum as final_sum.

Using Kadane’s Algorithm with Hashing

we can use hashing in above approach to find if an element is there in current selected subarray by using hash, this will give us searching in O(1) , to overall time complexity will be O(n).

#Code(C++)

If you have any question or any problem please comment or contact us.