1732. Find the Highest Altitude

문제

https://leetcode.com/problems/find-the-highest-altitude/description/

풀이

1. 처음 풀이 (prefix sum 배열 이용)

class Solution {
    public int largestAltitude(int[] gain) {
        int[] prefixSum = new int[gain.length]; 
        prefixSum[0] = gain[0];
        int answer = Math.max(0, prefixSum[0]); // 시작 고도인 0을 자연스레 포함시킴
        for(int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i-1] + gain[i]; 
            answer = Math.max(answer, prefixSum[i]);
        }

        return answer;
    }
}

• 배열을 쭉 순회하면서, 얻을 수 있는 최대 포인트 (최대합)을 구하는 문제
  • prefix sum으로 배열 index 까지의 합을 구한 뒤, 최대값을 return 해주면 된다.
• 이전(i-1)까지의 합으로 현재 인덱스까지의 합을 구해야하므로 i = 1부터 시작
  • prefixSum[0]의 값 = gain[0]
  • answer = Math.max(0, prefixSum[0])으로 시작 고도인 0을 자연스레 포함시킴

• 시간 복잡도 O(N), 공간 복잡도 O(N)
• 어차피 prefixSum을 한번만 이용하니까 for문 내에서 sum을 직접 구하면 공간 복잡도 O(1)으로 풀 수 있을듯

2. 다른 풀이 (공간복잡도 O(1))

class Solution {
    public int largestAltitude(int[] gain) {
        int sum = 0;
        int answer = 0; // 시작 고도인 0을 자연스레 포함시킴
        for(int i = 0; i < gain.length; i++) {
            sum += gain[i];
            answer = Math.max(answer, sum);
        }
        return answer;
    }
}

• 공간도 절약되고, 코드도 훨씬 간단해진다!