Question Asked in My previous Interview

[JasonHunts]

Maximum Profit in Job Scheduling

Problem Statement:
Given an array arr, find the maximum sum of a subarray where at most one element can be deleted.

Example:
Input:

arr = [1, -2, 0, 3]

Output: 4
Explanation: The subarray [1, 0, 3] has the maximum sum.

[Hunterdii]

Approach 1: Two Passes with (Kadane's Algorithm)

Explanation:
This approach extends Kadane's Algorithm to handle the case of one deletion. The idea is to:

1. Compute the maximum subarray sum ending at each index from left to right (forward pass).
2. Compute the maximum subarray sum starting at each index from right to left (backward pass).
3. Combine results to consider the case where one element is deleted, maximizing the sum of the subarray formed by skipping one element.

Algorithm Steps:

1. Calculate left[i]: Maximum subarray sum ending at index ii (standard Kadane's from left to right).
2. Calculate right[i]: Maximum subarray sum starting at index ii (Kadane's from right to left).
3. For each index ii, compute the result by considering:
   • Maximum sum without deletion.
   • Maximum sum by skipping the element at ii (combine left[i-1] and right[i+1]).

Code:

def maximumSum(arr):
    n = len(arr)
    if n == 1:
        return arr[0]

    # Step 1: Compute max sum ending at each index (left to right)
    left = [0] * n
    left[0] = arr[0]
    for i in range(1, n):
        left[i] = max(left[i-1] + arr[i], arr[i])

    # Step 2: Compute max sum starting at each index (right to left)
    right = [0] * n
    right[-1] = arr[-1]
    for i in range(n-2, -1, -1):
        right[i] = max(right[i+1] + arr[i], arr[i])

    # Step 3: Calculate the maximum sum
    maxSum = max(left)  # Maximum without deletion
    for i in range(1, n-1):
        maxSum = max(maxSum, left[i-1] + right[i+1])  # Maximum with one deletion

    return maxSum

Complexity:

• Time Complexity: O(n)O(n) — Two passes for left and right.
• Space Complexity: O(n)O(n) — To store left and right arrays.

Approach 2: Optimized Sliding Window with One Pass

Explanation:
Instead of maintaining two arrays (left and right), keep track of:

1. The maximum sum ending at the current index without deletion (noDelete).
2. The maximum sum ending at the current index with one deletion (oneDelete).

This reduces the space complexity while maintaining the correctness of the algorithm.

Code:

def maximumSum(arr):
    n = len(arr)
    if n == 1:
        return arr[0]

    noDelete = arr[0]  # Maximum sum without deletion
    oneDelete = 0      # Maximum sum with one deletion
    maxSum = arr[0]    # Overall maximum sum

    for i in range(1, n):
        oneDelete = max(oneDelete + arr[i], noDelete)  # Either extend oneDelete or use noDelete
        noDelete = max(noDelete + arr[i], arr[i])     # Standard Kadane's
        maxSum = max(maxSum, noDelete, oneDelete)     # Update global max

    return maxSum

Complexity:

• Time Complexity: O(n)O(n) — Single pass.
• Space Complexity: O(1)O(1) — Only variables are used.

Approach 3: Divide and Conquer

Explanation:
This approach splits the array recursively into two halves:

1. Compute the maximum subarray sum in the left half.
2. Compute the maximum subarray sum in the right half.
3. Compute the maximum subarray sum crossing the midpoint (handling deletion).

Algorithm Steps:

1. Use a recursive function that divides the array into halves.
2. For each segment, compute:
   • Maximum subarray sum without deletion in left and right halves.
   • Maximum subarray sum crossing the midpoint with or without deletion.
3. Return the maximum of all three cases.

Code:

def maximumSum(arr):
    def divideAndConquer(left, right):
        if left == right:
            return arr[left]

        mid = (left + right) // 2

        # Divide: Solve for left and right halves
        leftMax = divideAndConquer(left, mid)
        rightMax = divideAndConquer(mid + 1, right)

        # Conquer: Solve for crossing subarray
        leftCrossMax, rightCrossMax = float('-inf'), float('-inf')
        temp = 0

        # Left crossing sum
        for i in range(mid, left - 1, -1):
            temp += arr[i]
            leftCrossMax = max(leftCrossMax, temp)

        temp = 0
        # Right crossing sum
        for i in range(mid + 1, right + 1):
            temp += arr[i]
            rightCrossMax = max(rightCrossMax, temp)

        crossingSum = leftCrossMax + rightCrossMax

        # Conquer with one deletion
        oneDeleteMax = max(leftCrossMax, rightCrossMax)

        return max(leftMax, rightMax, crossingSum, oneDeleteMax)

    return divideAndConquer(0, len(arr) - 1)

Complexity:

• Time Complexity: $O(nlog⁡n)O(n \log n)$ — Divide and conquer involves splitting the array and linear merging.
• Space Complexity: $O(log⁡n)O(\log n)$ — Recursive stack.

Approach 4: Prefix and Suffix Sum

Explanation:
Use prefix and suffix sums to evaluate the maximum subarray sum:

1. Calculate prefix sum (prefixMax) and suffix sum (suffixMax).
2. Consider skipping each element and combining the prefix and suffix sums on either side of the skipped element.

Code:

def maximumSum(arr):
    n = len(arr)
    prefixMax = [0] * n
    suffixMax = [0] * n

    # Compute prefixMax
    prefixMax[0] = arr[0]
    for i in range(1, n):
        prefixMax[i] = max(prefixMax[i-1] + arr[i], arr[i])

    # Compute suffixMax
    suffixMax[-1] = arr[-1]
    for i in range(n-2, -1, -1):
        suffixMax[i] = max(suffixMax[i+1] + arr[i], arr[i])

    # Calculate maximum sum
    maxSum = max(prefixMax)  # Maximum without deletion
    for i in range(1, n-1):
        maxSum = max(maxSum, prefixMax[i-1] + suffixMax[i+1])  # Maximum with one deletion

    return maxSum

Complexity:

• Time Complexity: O(n)O(n) — Two passes for prefix and suffix sums.
• Space Complexity: O(n)O(n).

Conclusion:

• Sliding Window (Approach 2) is the most efficient for this problem due to its O(1)O(1) space usage.
• Other approaches, like Divide and Conquer or Prefix/Suffix, offer clarity and alternative problem-solving methods but at the cost of additional space or complexity.

[JasonHunts]

Great this answer is Worth @Hunterdii I just wanted to say a big THANK YOU for the incredible explanation you provided! 🙌 The way you broke down the problem and explained the solution step by step was not only clear but also super helpful. Your approach to tackling the question was thorough, and I really appreciate the effort you put into making it easy to understand.

Honestly, it felt like you went above and beyond, especially with the detailed explanation and optimized code solutions. It’s clear that you have a deep understanding of the topic, and it inspires me to learn more.

Thanks again for taking the time to help—I’m lucky to have a friend like you! 😊