Maximum Absolute Sum of Any Subarray - Leetcode 1749 - Python

0:00 - Intro
1:00 - Understand Problem
5:55 - Drawing Explanation
11:49 - Dry Run
15:28 - Coding Explanation

leetcode 1749

#neetcode #leetcode #python

[legendrebel]

An easier approach could be finding negative max sum and positive max sum like in kadane's algo and then take the max of absolute positive max sum and absolute maximum negative sum.
Complexity will be O(n).

[mingbee]

Everytime I come to Neetcode video, I go straight to the code part, fail to understand the logic by reading the code, and eventually go back to the front to watch the whole explanation😂

[fixyourshoes]

I had a problem understanding the prefix sums solution and had solved it with Kadane's. However once you realize that subtracting any two numbers from prefix sums gives you a sum of some subarray, the problem can be transformed into finding the biggest difference between any two numbers in the array. Which is obviously finding the maximum and minimum and subtracting one from another. This can be further optimized as you don't have to keep the whole prefix sums array, and calculate these values as you go.

[bhilaibiryanihouse-jm]

@neetcode, I humbly request you to make a video on the Aggressive Cows problem. While this question is not on LeetCode, there are similar ones available. In fact, Question 4 from this week's contest was related to it. I wanted to know your thought process and intuition.

PLEASE PLEASE PLEASE.

[anand-zkuj]

Hey neetcode I need your advise, that leetcode has banned me from contest bcoz they say that I have used external tool like chatgpt, I didn't even used it. I sent them a request regarding unban how much time did it will take to resolve the issue. This is a mistaken ban. 😢😢

[Kal_be_kal]

⚠ You don't have to update the res in each iteration, you can just update it after the for loop once like this (res = max_pre - min_pre)

[Kiberbulochka]

You always just in time, with those videos-solutions, when I try to do the same Leetcode problems.
Thank you!

[ajaymishra]

i did this one as




math.max(negativemaxsum, positivemaxsum)
time complexity = 2n

[swastiktiwari]

In this problem, what we really need is highest positive distance from origin and highest negative distance from origin so that result = highest positive distance from origin - highest negative distance from origin in your solution, the calculation of res for every n in nums is a redundant step the end of loop we could simply return max_pre - min_pre

class Solution {
public:
int maxAbsoluteSum(vector<int>& nums) {
int min_Presum = 0, max_Presum = 0, cumSum = 0;
for(const int& num: nums) {
cumSum+=num;
min_Presum = min(min_Presum, cumSum);
max_Presum = max(max_Presum, cumSum);
}
return max_Presum - min_Presum;
}
};

[howardlam]

I remember doing another very similar problem but can't remember on top of my head what it was. Also to do with negative and positive maximums.

[Mahidhar-wp]

Not need of calculating res at every index.
class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
res, prefix_max, prefix_min = 0, 0, 0
curr = 0
for n in nums:
curr += n
prefix_max = max(prefix_max, curr)
prefix_min = min(prefix_min, curr)
return prefix_max - prefix_min

[Frustrated-Indian-]

You don't sleep or GMT is near you?

[YashGupta-tyhn]

A much easier solution is kadane's algo
class Solution:
def maxAbsoluteSum(self, nums: List[int]) -> int:
psum, nsum = 0, 0
ans = 0
for num in nums:
psum += num
nsum += num
if psum < 0:
psum = 0
if nsum > 0:
nsum = 0
ans = max(ans, abs(nsum), psum)
return ans

[akshayreddy]

I just negetaed every number and ran kadanes 2nd time ans is max of 2 kadanes

[treyquattro]

as soon as I read the hint that said Kadane's I was in like Kaflynn. Until then I didn't really have a clue.

[samyakmahapatra]

I tried a solution and it worked pls lemme know this is always correct or not so here it goes



Max absolute sum of subarray, for this first we can find max sum of subarray in the actual array.But note we can have max abs sum when we take lot of negatives as well or when lot of negatives over some positives but this particular abs sum can be written as max subarray sum of the array having negative elements as original array. So for final ans we just need to compare both the sums.
vector<int>temp;
for(int i=0;i<nums.size();i++){
temp.push_back(-nums[i]);
}
int ans1=maxsum(nums), ans2=maxsum(temp);
return max(ans1, ans2);

[techandmore]

Why not run kedanes algorithm twice? Ez O(n)