# 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

**, each representing one element of array.**

*n elements*## 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.