LeetCode Problem 1749

Link of the Problem to try -: Link

You are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr).

Return the maximum absolute sum of any (possibly empty) subarray of nums.

Note that abs(x) is defined as follows:

1. If x is a negative integer, then abs(x) = -x.
2. If x is a non-negative integer, then abs(x) = x.

Example 1:

Example 2:

Constraints:

1. 1 <= nums.length <= 105
2. -104 <= nums[i] <= 104

My Thinking

So, in this question what exactly we have to do what actual logic behind it to solve this question is that like you need to first find out the maximum sum of sub array via kadane's algorithm also find the minimum sum of subarray and then compare both numbers ignore the negative signs of it and then return the maximum number that is what the question want and we have to solve in it.

Kadane's Algorithm

This algorithm is highly efficient, solving the problem in a single pass with a time complexity of O(n), not O(1) constant time, as the algorithm must iterate through all n elements of the input array.

The core principle is based on the idea that any negative prefix sum acts as a 'debt' that subsequent positive numbers must overcome. The strategy is to always pursue the maximum sum. If the running sum becomes negative at any point, it is reset to zero, effectively 'discarding' the previous negative sequence, and the search for a new maximum sum begins with the next element.

Here is a video for more better understanding

Solution:

Here is the solution for this quesiton in java by Kadane's Algorithm