Subarray Problems (Maximum sum, K-sum, Longest sequence)

Maximum Subarray (LeetCode 53)

Kadane's Algorithm: Optimize the local maximum to find the global maximum.

int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int maxSum = nums[0], curSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        // Either extend the previous subarray or start fresh from the current element
        curSum = Math.max(nums[i], curSum + nums[i]);
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

DP Definition: Let dp[i] be the maximum subarray sum ending at index i.

• dp[i] = max(nums[i], dp[i-1] + nums[i])

Divide and Conquer Approach (O(n log n)):

• Recursively calculate the max subarray of the left half, the right half, and the segment crossing the midpoint.

Subarray Sum Equals K (LeetCode 560)

Using Prefix Sum + Hash Map achieves O(n) complexity:

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);  // Initial state for empty prefix
    int count = 0, sum = 0;
    for (int n : nums) {
        sum += n;
        // If sum - k exists in the map, there's a subarray ending here with sum k
        count += prefixCount.getOrDefault(sum - k, 0);
        prefixCount.merge(sum, 1, Integer::sum);
    }
    return count;
}

Variant: Longest Subarray Sum equal to K (Store the earliest occurrence of each prefix sum to maximize length):

int maxSubArrayLen(int[] nums, int k) {
    Map<Integer, Integer> firstIndex = new HashMap<>();
    firstIndex.put(0, -1);
    int maxLen = 0, sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (firstIndex.containsKey(sum - k))
            maxLen = Math.max(maxLen, i - firstIndex.get(sum - k));
        // Keep only the first occurrence to maximize the result of the subtraction
        firstIndex.putIfAbsent(sum, i);
    }
    return maxLen;
}

Maximum Product Subarray (LeetCode 152)

Unlike addition, the product can flip between very large and very small when encountering negative numbers. We must track both the maximum and minimum products up to each point:

int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int maxProd = nums[0], minProd = nums[0], res = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int n = nums[i];
        // If n is negative, max becomes min and min becomes max when multiplied
        int tempMax = Math.max(n, Math.max(maxProd * n, minProd * n));
        int tempMin = Math.min(n, Math.min(maxProd * n, minProd * n));
        maxProd = tempMax;
        minProd = tempMin;
        res = Math.max(res, maxProd);
    }
    return res;
}

Longest Consecutive Sequence (LeetCode 128)

Requires O(n) complexity. Use a HashSet for O(1) lookups to avoid sorting:

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);

    int longest = 0;
    for (int n : set) {
        // Only start checking if the current number is the BEGINNING of a sequence
        if (!set.contains(n - 1)) {
            int cur = n, len = 1;
            while (set.contains(++cur)) len++;
            longest = Math.max(longest, len);
        }
    }
    return longest;
}

Summary Comparison