[LeetCode] 1749. Maximum Absolute Sum of Any Subarray (Python)

 

 

난이도: Medium

Problem Description

---

 

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:

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

 

Problem Example

---

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.

Example 2:

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.

 

Constraints

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

 

✏️ Solution

---

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        local_max = nums[0]
        local_min = nums[0]
        answer = abs(nums[0])

        for i in range(1, len(nums)):
            local_max = max(nums[i], nums[i] + local_max)
            local_min = min(nums[i], nums[i] + local_min)

            answer = max(answer, local_max, abs(local_min))

        return answer

 

`Kadane's algorithm`을 통해 쉽게 해결할 수 있었다.

 

`Kadane's algorithm`은 [알고리즘] Maximum Subarray Sum - Kadane's Algorithm (카데인 알고리즘)에서 확인할 수 있다.

 

나의 접근법은 주어진 nums에서 부분 배열의 합 중 최대인 것을 구하고, 주어진 nums에서 부분 배열의 합 중 최소인 것을 구했다.

 

그리고 이들을 절대값을 취해 더 큰 값을 정답으로 return 하였다. ( ex) max: 5, min: -6  --> max(abs(5), abs(-6) --> 6)

 

 

 

 

⚙️ Runtime & Memory

---

 

 

Beats 38.54%... ㅜㅜ

 

---

문제: 1749. Maximum Absolute Sum of Any Subarray

 

깃허브: github

algorithmPractice/LeetCode/1849-maximum-absolute-sum-of-any-subarray at main · laewonJeong/algorithmPractice