# Given a non-empty array of length n with non-negative elements. Write a program to find and return the maximum sum of a contiguous

subarray of the given array such that no two elements are repeated in the subarray.

`Input: 1 2 3 3 4 5 2 1Output: 15Explanation: Subarray from index 3 to 7 constitutes the sum 15(3+4+5+2+1)`

Approach:

We will use two pointers i and j. We will use HashSet to store the elements of the ARRAY and update sum and j.

And once we encounter an element which is already in our set, we will remove all the elements from set preceding the repeated element, while incrementing i and updating our sum variable.

Code:

`import java.io.*;import java.lang.Math;import java.util.*;public class Main{	//function to calculate maximum sum array  	public static int longestSubarray(int[] arr) {        int i = 0, j = 1, currLength = 1;    HashSet<Integer> set = new HashSet<Integer>();    set.add(arr[0]);      	int sum= arr[0];// current max sum	int maxsum=sum;// GLobal maximum sum        while (i < arr.length - 1 && j < arr.length) {      	// update sum and maxsum and increment j        if (!set.contains(arr[j])) {            sum=sum+arr[j];			maxsum=Math.max(sum,maxsum);            set.add(arr[j++]);        }      	// update sum and increment i and remove arr[i] from set        else {			sum-=arr[i];            set.remove(arr[i++]);           }    }        return maxsum;	}    //Driver code  public static void main(String[] args) {	    int arr[] = new int[]{ 1,2,3,4,1,1,9,4 }; 		int ans = longestSubarray(arr);		System.out.println(ans);	}  }`

Complexity:

• Time: O(n)
• Auxiliary Space: O(n)

--

--