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.
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.
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
5 5 5 4 max_sum:5
There may be couple of approaches to solve that problem,
first might be the brute force approach which could be implemented in O(n³) .
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.
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).
If you have any question or any problem please comment or contact us.