Untitled

 avatar
unknown
plain_text
22 days ago
2.0 kB
2
Indexable
class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length; // Store the length of the array.
        int[] leftMaxSum = new int[n]; // Maximum subarray sum ending at each index from the left.
        int[] rightMaxSum = new int[n]; // Maximum subarray sum starting at each index from the right.
        int maxSum = Integer.MIN_VALUE; // Initialize maxSum with the smallest possible integer value.
      
        // Calculate the maximum subarray sum from the left and find the max subarray sum without deletion.
        int currentSum = 0; // Initialize a variable to keep track of the current summation.
        for (int i = 0; i < n; ++i) {
            currentSum = Math.max(currentSum, 0) + arr[i]; // Calculate the sum while resetting if negative.
            leftMaxSum[i] = currentSum; // Store the maximum sum up to the current index from the left.
            maxSum = Math.max(maxSum, leftMaxSum[i]); // Update the maximum subarray sum seen so far.
        }
      
        // Calculate the maximum subarray sum from the right.
        currentSum = 0; // Reset the currentSum for the right max subarray calculation.
        for (int i = n - 1; i >= 0; --i) {
            currentSum = Math.max(currentSum, 0) + arr[i]; // Calculate the sum while resetting if negative.
            rightMaxSum[i] = currentSum; // Store the maximum sum up to the current index from the right.
        }
      
        // Check the maximum sum by considering deleting one element from the array.
        for (int i = 1; i < n - 1; ++i) {
            // Sum of subarrays left to i excluding arr[i] and right to i excluding arr[i] provides a sum
            // for the array with arr[i] deleted. Update maxSum if this sum is larger.
            maxSum = Math.max(maxSum, leftMaxSum[i - 1] + rightMaxSum[i + 1]);
        }
      
        return maxSum; // Return the maximum subarray sum with at most one element deletion.
    }
}
Leave a Comment