[leet code] 1749. Maximum Absolute Sum of Any Subarray (JAVA)

1749. Maximum Absolute Sum of Any Subarray

🗒️알고리즘 분류

#Kadane's algorithm #prefix sum #누적합

📌기억할 만한 포인트

배열의 인덱스 i 까지의 누적 합(PrefixSum)을 s[i] 라고 정의하면

• 누적 합(PrefixSum): s[i] = nums[0]+nums[1]+⋯+nums[i]

부분 배열의 합 표현: s[j]−s[i]

• 인덱스 i 부터 j 까지의 부분 배열의 합은 두 누적 합의 차이로 표현됩니다.
• s[j]−s[i] (단, j>i)로 표현됩니다.
• 이때, s[j]와 s[i]는 누적 합 배열의 원소입니다.

집합 {s[0],…,s[n−1]} 에서 두 수의 차이의 절댓값의 최댓값은 max(s)−min(s)와 같습니다.

따라서, 배열의 모든 누적 합 중 최댓값과 최솟값의 차이가 부분 배열 합의 절댓값 최댓값과 같다

📝 1번째 풀이 코드(JAVA)

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int maxSum = nums[0];
        int minSum = nums[0];
        int max = nums[0];
        int min = nums[0];

        for (int i = 1; i < nums.length; ++i) {
            max = Math.max(nums[i], max+nums[i]);
            min = Math.min(nums[i], min+nums[i]);
            maxSum = Math.max(maxSum, max);
            minSum = Math.min(minSum, min);
        }

        return Math.abs(maxSum) > Math.abs(minSum) ? Math.abs(maxSum) : Math.abs(minSum);
    }
}

📝 2번째 풀이 코드(JAVA)

class Solution {

    public int maxAbsoluteSum(int[] nums) {
        int minPrefixSum = 0, maxPrefixSum = 0;
        int prefixSum = 0;

        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];

            minPrefixSum = Math.min(minPrefixSum, prefixSum);
            maxPrefixSum = Math.max(maxPrefixSum, prefixSum);
        }

        return maxPrefixSum - minPrefixSum;
    }
}

⏰총 풀이시간

• 40분