Maximum Sum Contiguous subarray with unique elements.

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 1
Output: 15
Explanation: 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)

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Localization is the new decentralization

Iterative Testing & Trying DAO Tools

Data ETL using Apache Beam — Part Two…

Amazon Api Gateway Multiple Secure Domains | Multiple Certificates

Introducing Atlantis

Summer 2021 — Task 11

Top 5 Best IDEs for Web Development

A Beta to Help You Create a Data and AI Platform on Your Terms

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abhinay Gupta

Abhinay Gupta

More from Medium

Why Learning Programming Takes Time

4-in-1 Priority First Search in Python: BFS, DFS, Prim’s, and Dijkstra’s algorithms

I have Cleared My First Technical Interview, Feeling Proud! Wanna Know How?

Java Lesson 20: Lines, Colors and Basic Java Graphics