Problems

Maximum Subarray (Python)

def max_subarray(nums):

    max_so_far = float('-inf')  # Initialize with negative infinity

    max_ending_here = 0

    for num in nums:

        max_ending_here = max(0, max_ending_here + num)

        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

max_sum = max_subarray(nums)

print(f"The maximum sum of a contiguous subarray is: {max_sum}")  # Output: 6

Maximum Subarray (Java)

public class MaxSubarray {

    public static int maxSubArray(int[] nums) {

        int maxSoFar = Integer.MIN_VALUE;

        int maxEndingHere = 0;

        for (int num : nums) {

            maxEndingHere = Math.max(0, maxEndingHere + num);

            maxSoFar = Math.max(maxSoFar, maxEndingHere);

        }

        return maxSoFar;

    }

    public static void main(String[] args) {

        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int maxSum = maxSubArray(nums);

        System.out.println("The maximum sum of a contiguous subarray is: " + maxSum); // Output: 6

    }

}

Longest Substring Without Repeating Characters (Python)

def lengthOfLongestSubstring(s):

    lastSeen = {}      # Dictionary to store last seen index of each character

    start = 0           # Start index of current substring

    maxLength = 0      # Length of the longest substring found so far

    for i, char in enumerate(s):

        if char in lastSeen and lastSeen[char] >= start:

            start = lastSeen[char] + 1  # Move the start to after the last seen duplicate

        lastSeen[char] = i              # Update the last seen index of the character

        maxLength = max(maxLength, i - start + 1)  

    return maxLength