[LCS] Longest Consecutive Subsequence Medium

Problem Statement

Given an array, the aim is to find the longest consecutive subsequence.
For eg. In [1, 3, 4, 5, 8, 0, 2], LCS is 0, 1, 2, 3, 4, 5 ⇒ LCS is 5.

Algorithm

Let us consider the following example
In order to get the LCS, let’s visualize the elements in an imaginary line.
Here, we can observe that there are 3 possible sub sequences.
In order to start a new subsequence, a number should not have its previous number in the array, Eg. 2 does not have 1 in the array but 3 has 2 in the array.
So, the aim here is to find the start of the subsequence in each iteration, and then find its length
To achieve this, we first need to iterate through all the elements of the array and store the elements in a hashmap so that it would be easier to fetch the previous / next elements of the sequence in O(1) time.
Next, we iterate
Here, element at i is 2, We check from the map if its previous number 1 is present or not.
1 is not present, which makes 2 as one of the start of a subsequence. Now, we check how long the subsequence goes by searching for the next elements of the sequence in the map.
Now we reached a point where one of the numbers in the sequence is not present in the array, so we end the iteration here, update the max lcs with current lcs, and increment i.
9 is another start of a subsequence as 8 was not present. So we check its length.
Here, 10 is not present, which makes the length of subsequence as 1. This is less than our current max lcs (5). We increment index i and proceed.
Element 6 cannot be the start of a sequence because its previous element 5 is present in the array. We increment index i and proceed.
7 is not present, making 8 as the start of a sequence.
9 is present, making the current sequence length as 2.
The next element of the sequence (10) is not present, hence the sequence ends with length 2. This is still less than our current max lcs (5). We increment i and proceed.
3 is present making the element 4 a part of another subsequence. We increment index i and proceed.
2 is present making the element 3 a part of another subsequence. We increment index i and proceed.
4 is present making the element 5 a part of another subsequence. We increment index i and proceed.
-1 is not present, meaning 0 is the start of a new subsequence.
The next subsequence element is not present for 0, hence the length of subsequence starting with 0 is 1, which is still less than the current max lcs (5).
We have now reached the end of iteration, and the max lcs is 5.

Code

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = Integer.MIN_VALUE;
        int currentSum = 0;
        
        for(int i = 0; i < nums.length; i++) {
            int num = nums[i];
            currentSum += num;

            sum = Math.max(currentSum, sum);

            if (currentSum < 0) {
                currentSum = 0;
                continue;
            }
        }

        return sum;
    }
}