Maximum Absolute Sum of Any Subarray | Leetcode 1749

//Solution-1: Using Kadane's Algorithm
class Solution {
    int maxSumSubarrayKadanes(vector<int>& nums){
        int max_sum = INT_MIN;
        int curr_sum = 0;
        for(int ele: nums){
            curr_sum += ele;
            max_sum = max(max_sum,curr_sum);
            if(curr_sum<0)
                curr_sum = 0;
        }
        return max_sum;
    }
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int max_sum_subarray = maxSumSubarrayKadanes(nums);
        
        //Flip all signs
        for(int i=0;i<nums.size();++i)
            nums[i] = (-1)*nums[i];
        
        int min_sum_subarray = maxSumSubarrayKadanes(nums);
        return max(max_sum_subarray,min_sum_subarray);
    }
};

//Solution-2: Prefix Sum
class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int min_point = 0;
        int max_point = 0;
        int prefix_sum = 0;
        for(int ele: nums){
            prefix_sum += ele;

            min_point = min(min_point,prefix_sum);
            max_point = max(max_point,prefix_sum);
        }
        return max_point - min_point;
    }
};

/*
//Solution-1: Kadane's Algorithm
class Solution {
    private int maxSumSubarrayKadanes(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int currSum = 0;
        for (int num : nums) {
            currSum += num;
            maxSum = Math.max(maxSum, currSum);
            if (currSum < 0) {
                currSum = 0;
            }
        }
        return maxSum;
    }

    public int maxAbsoluteSum(int[] nums) {
        int maxSumSubarray = maxSumSubarrayKadanes(nums);

        // Flip all signs
        for (int i = 0; i < nums.length; i++) {
            nums[i] = -nums[i];
        }

        int minSumSubarray = maxSumSubarrayKadanes(nums);
        return Math.max(maxSumSubarray, minSumSubarray);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, -3, 2, 3, -4}; // Example input
        System.out.println(solution.maxAbsoluteSum(nums));
    }
}

//Solution-2: Prefix Sum
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int minPoint = 0;
        int maxPoint = 0;
        int prefixSum = 0;
        for (int num : nums) {
            prefixSum += num;
            minPoint = Math.min(minPoint, prefixSum);
            maxPoint = Math.max(maxPoint, prefixSum);
        }
        return maxPoint - minPoint;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, -3, 2, 3, -4}; // Example input
        System.out.println(solution.maxAbsoluteSum(nums));
    }
}

#Python
//Solution-1: Kadane's Algorithm
class Solution:
    def maxSumSubarrayKadanes(self, nums: list[int]) -> int:
        max_sum = float('-inf')
        curr_sum = 0
        for num in nums:
            curr_sum += num
            max_sum = max(max_sum, curr_sum)
            if curr_sum < 0:
                curr_sum = 0
        return max_sum

    def maxAbsoluteSum(self, nums: list[int]) -> int:
        max_sum_subarray = self.maxSumSubarrayKadanes(nums)

        # Flip all signs
        nums = [-num for num in nums]

        min_sum_subarray = self.maxSumSubarrayKadanes(nums)
        return max(max_sum_subarray, min_sum_subarray)

# Example usage
solution = Solution()
nums = [1, -3, 2, 3, -4]  # Example input
print(solution.maxAbsoluteSum(nums))

//Solution-2: Prefix Sum
class Solution:
    def maxAbsoluteSum(self, nums: list[int]) -> int:
        min_point = 0
        max_point = 0
        prefix_sum = 0
        for num in nums:
            prefix_sum += num
            min_point = min(min_point, prefix_sum)
            max_point = max(max_point, prefix_sum)
        return max_point - min_point

# Example usage
solution = Solution()
nums = [1, -3, 2, 3, -4]  # Example input
print(solution.maxAbsoluteSum(nums))

*/