Untitled
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