Maximum Absolute Sum of Any Subarray | Leetcode 1749

This video explains Maximum Absolute Sum of Any Subarray using the most optimal prefix sum and kadanes algorithm.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone]
---------------------------------------------------------------------------------------------------------------------------------------------------------------

[abudanish]

nice work man, we cpp coders are thankful!

[JuicyMN]

just by looking at the graph in your thumbnail, could figure out the approach haha, thats how effective your explanations are.

[chandramoulyv]

Thank you so much sir, i can easily understand the logic

[AnkitMishra-ysfb]

One optimization, no need to run one more loop to make the number negative

int maxSum(vector<int>& v){
int curSum = 0;
int maxSum = INT_MIN;
for(int &i:v){
curSum+=i;
maxSum = max(maxSum, curSum);
if(curSum < 0)
curSum = 0;
i*=(-1);
}
return maxSum;
}
int maxAbsoluteSum(vector<int>& nums) {
int pos = maxSum(nums);
int neg = maxSum(nums);
int res = max(pos, neg);
return abs(res);
}

[freecourseplatformenglish]

😉❤. mine appraoch is similar to calculating max and min prefix sum them subtract it to curr sum based on if currSum is positive or negative.
Happy to solve this after struggling to solve tomorrow's problem.

[arush]

//this also works in o(n) and has a 0ms solution and also easy to understand just combined the kandane and reverse kandane algo thing in one loop (only click read more to see code)


class Solution
{
public:
int maxAbsoluteSum(vector<int> &nums)
{
int n = nums.size();
if (n == 1)
return abs(nums[0]);
int minsum = INT_MAX;
int maxsum = INT_MIN;
int currmax = 0;
int currmin = 0;

for (int i = 0; i < n; i++)
{
currmax += nums[i];
currmin += nums[i];
maxsum = max(maxsum, currmax);
minsum = min(minsum, currmin);
if (currmax < 0)
{
currmax = 0;
}
if (currmin > 0)
{
currmin = 0;
}
}

maxsum = abs(maxsum);
minsum = abs(minsum);
return max(maxsum, minsum);
}
};

[wierdo]

for the graph approach when min and max=0 it is crct but initially I initialized them as MAX_VALUE and MIN_VALUE and failed at a tc can you reason it ?

[paritoshsep]

I found the solution to this problem through your video. However, you didn't explain the intuition behind the approach. You directly stated that we need to find the difference between the minimum and maximum elements of the subarray sum, but you didn’t walk us through how we arrived at this conclusion. While we might forget the exact solution over time, understanding the underlying intuition helps in recalling and applying it in the future. This crucial explanation is missing in the video.

[GurwinderSingh-mw]

Who will tell the intuition of second approach?