Leetcode Problem:
Summary
- Given an integer array, find the maximum absolute sum of any subarray.
Approach
- Use two pointers to track the maximum and minimum prefix sum, then return the maximum of the two absolute values.
Complexity
- O(n) where n is the number of elements in the array
Explanation
- The solution works by iterating over the array twice, once to find the maximum prefix sum and once to find the minimum prefix sum
- The maximum prefix sum is updated whenever a positive number is encountered, and the minimum prefix sum is updated whenever a negative number is encountered
- The maximum of the two absolute values is then returned as the result.
Solution Code:
class Solution {
public:
int maxAbsoluteSum(vector& nums) {
int r = 0;
int l = 0;
int plusMax = 0;
int prefixSum = 0;
for(int num : nums){
prefixSum += num;
if(prefixSum < 0) prefixSum = 0;
plusMax = max(plusMax, prefixSum);
}
int minusMin = 0;
prefixSum = 0;
for(int num:nums){
prefixSum += num;
if(prefixSum > 0) prefixSum = 0;
minusMin = min(minusMin, prefixSum);
}
return plusMax > abs(minusMin) ? plusMax : abs(minusMin);
}
};
class Solution {
public:
int maxAbsoluteSum(vector& nums) {
int r = 0;
int l = 0;
int plusMax = 0;
int prefixSum = 0;
for(int num : nums){
prefixSum += num;
if(prefixSum < 0) prefixSum = 0;
plusMax = max(plusMax, prefixSum);
}
int minusMin = 0;
prefixSum = 0;
for(int num:nums){
prefixSum += num;
if(prefixSum > 0) prefixSum = 0;
minusMin = min(minusMin, prefixSum);
}
return plusMax > abs(minusMin) ? plusMax : abs(minusMin);
}
};
'알고리즘' 카테고리의 다른 글
| Final Array State After K Multiplication Operations I (0) | 2025.02.27 |
|---|---|
| Maximum Average Pass Ratio (0) | 2025.02.27 |
| Number of Sub-arrays With Odd Sum (0) | 2025.02.26 |
| Continuous Subarrays (0) | 2025.02.25 |
| Find Score of an Array After Marking All Elements (0) | 2025.02.25 |
짬뽕얼큰하게
