1749. Maximum Absolute Sum of Any Subarray

Описание: 1749. Maximum Absolute Sum of Any Subarray

How to approach such question
=============================

Absolute means if the integer is negative absolute makes it positive
Let us see the question which is a medium level question. Such problem can be solved using kadane algorithm. If anyone is not familiar with it please see our previous video on this using below link

   • Kadane Algorithm Explained  

Let us break absolute sum into below steps
===================================

1.) Find the maximum sum subarray of given array using kadance algorithm. See the solution from below code
2.) Now take the negative of the array. You can do this step using list comprehension and pass it to kadane to find the maximum sum subarray. See the solution from here
3.) Now find the max of step 1 and step2. See the solution from here. This is the final answer

Let us talk about time and space complexity
===========================================

Time complexity
=============
1.) kadance algo will be implemented in O(n)
2.) Since we are creating negative of array using list comprehension and list comprehension consist of loop and append operation which occurs in O(n**2)

Space complexity
================

1.) Since we are using another another negative array to compute absolute sum subarray hence it will take O(n) space.

Link for the code:
==============

https://github.com/AISangam/kadane_al...

If you like the video, you may follow us at following platforms

Facebook: https://www.facebook.com/aisangam4you...
Linkedln:   / ai-sangam-819662164  
Skype: live:aisangamofficial
Instagram: https://www.instagram.com/aisangamoff...

You may also put your query at
Gmail: [email protected]