2주차 2차 2 - LeetCode-Study-Team/solutions GitHub Wiki

53 Maximum Subarray

문제 요약

정렬되지 않은 배열 안의 연속된 값들의 최댓값 구하기. (최소 하나는 포함해야됨. 즉, 모두 음수일 경우, 제일 큰값 포함)

인풋데이터

int[] nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(maxSubArray(nums1)); // 답: 6

int[] nums2 = {1};
System.out.println(maxSubArray(nums2)); // 답: 1

int[] nums3 = {5, 4, -1, 7, 8};
System.out.println(maxSubArray(nums3)); // 답: 23

주의

  • 양수들로 연속된 부분을 찾으면 최댓값?
    • 마이너스 나온다고 항상 멈추면 안된다. (e.g. 200, -2, -4, -100, 10000)

시도 1

  • 1,2, ... n개씩 더해보기
    • 최대값 변수 만들고,
    • 1번째 iteration에서는 1개씩 연속된 합 비교
    • 2번째 iteration에서는 2개씩 연속된 합 비교
    • ...
    • n번째 iteration에서는 n개 연속된 합 비교
    • 문제
      • 계산값 또 계산
      • Plus, 코드가 안짜짐..

시도 2

  • 직관적 방법
  • input: -2, 2, 3, -4
public int maxSubArray(int[] nums) {
    int maxSum = Integer.MIN_VALUE; // -2147483648
    for (int i = 0; i < nums.length; i++) {
        int tempMaxSum = 0; // i 값이 포함된 모든 합계 중 최대값 찾기 위한 변수 
        for (int j = i; j < nums.length; j++) {
            tempMaxSum += nums[j];
            if (tempMaxSum > maxSum) maxSum = tempMaxSum;
            // if문 다른대안: maxSum = Math.max(tempMaxSum, maxSum);
        }
    }
    return maxSum;
}
  • 문제점: 시간 초과하여 실패 (testcase)
    • 이유: 계산한 것을 또 계산하는 비효율이 시간을 잡아먹은게 아닐까.
  • 시간 복잡도: O(n^2)
    • for 문 2번
  • 공간 복잡도: O(1)
    • maxSum과 tempMaxSum 변수 딱 두개만 사용하니

최적 풀이 1 - DP (카데인 알고리즘)

  • 카데인 알고리즘: 큰 문제를 서브문제로 나눠 푸는 것.
  • 이 풀이 돌아가는게 신기
  • 내생각
    • 특징: 양수가 나왔을때 전까지 합이 음수였으면, 그 전 연속 값들 합은 keeping 할 필요 x
  • 각 라운드
    • 특징: currentSubarray이 마이너스 되면 버려진다.
-2 1 -3 4 -1 2 1 -5 4
cur -2 1 -2 4 3 5 6 1 4
max -2 1 1 4 4 5 6 6 6 
class Solution {
    public int maxSubArray(int[] nums) {
        int currentSubarray = nums[0]; // 포인터 움직이면서 
        int maxSubarray = nums[0]; // 최대값

        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            currentSubarray = Math.max(num, currentSubarray + num);
            maxSubarray = Math.max(maxSubarray, currentSubarray);
        }

        return maxSubarray;
    }
}
  • 시간 복잡도: O(N)
    • 배열을 1번만 돈다
  • 공간 복잡도: O(1)
    • currentSubarray과 maxSubarray 변수 딱 두개만 사용하니

최적 풀이 2 - 분할 정복

  • 풀이1 보다 느리고 공간도 많이 쓰지만, 다른방법으로 풀어보는도 굿
  • 분할 정복 : 부분으로 나눠서 풀고 나중에 결합 (위 카데인 알고리즘하고 다를게 없는데?)
  • 풀이 설명
    • input: 5, -2, 1, -3, 4, -2, 1 경우
      • 배열 길이: 7
      • bestLeftSum: 4
      • bestRightSum: 3
      • bestCombinedSum: 4
      • leftHalf: 5
      • rightHalf: 4
      • 답: Math.max(bestCombinedSum, Math.max(leftHalf, rightHalf))
        • 즉, Math.max(4, Math.max(5, 4)); -> 5
    • input: 100, -90, -30, -10, 20, -50, 10 경우
      • 배열 길이: 7
      • bestLeftSum: 0
      • bestRightSum: 20
      • bestCombinedSum: 20
      • leftHalf: 100
      • rightHalf: 20
      • 답: Math.max(bestCombinedSum, Math.max(leftHalf, rightHalf))
        • 즉, Math.max(20, Math.max(100, 20)); -> 100
    • 함수
      • Math.floorDiv(left + right, 2) : 2로 나눠 내림
        • e.g. Math.floorDiv(7, 2) : 3
class Solution {
    private int[] numsArray;
    
    public int maxSubArray(int[] nums) {
        numsArray = nums;
        return findBestSubarray(0, numsArray.length - 1);
    }
    
    private int findBestSubarray(int left, int right) { // 0 6
        // 빈 배열 필터링
        if (left > right) {
            return Integer.MIN_VALUE;
        }
        
        int mid = Math.floorDiv(left + right, 2); // 중간값: 3
        int curr = 0;
        int bestLeftSum = 0;
        int bestRightSum = 0;
        
        // (왼쪽 - 가운데) - 오른쪽
        for (int i = mid - 1; i >= left; i--) { // 순서: 2 1 0 
            curr += numsArray[i];
            bestLeftSum = Math.max(bestLeftSum, curr);
        }
        
        curr = 0;
        
         // 가운데 부터 오른쪽으로 
        for (int i = mid + 1; i <= right; i++) { // 순서: 4 5 6
            curr += numsArray[i];
            bestRightSum = Math.max(bestRightSum, curr);
        }
        
        int bestCombinedSum = numsArray[mid] + bestLeftSum + bestRightSum;
        
        // 왼, 오른 쪽 각각 최댓값 가져오기
        int leftHalf = findBestSubarray(left, mid - 1);
        int rightHalf = findBestSubarray(mid + 1, right);
        
        return Math.max(bestCombinedSum, Math.max(leftHalf, rightHalf));
    }
}

팁

최댓값, 최솟값 문제들은 일단 DP를 고려해보자.

118 Pascal's Triangle

이미지

내 풀이

/**
     * Runtime: 0 ms, faster than 100.00% of Java online submissions for Pascal's Triangle.
     * Memory Usage: 36.8 MB, less than 83.77% of Java online submissions for Pascal's Triangle.
     */
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> firstLine = new ArrayList<>();
    firstLine.add(1);
    ans.add(firstLine);

    if (numRows == 1) {
        return ans;
    }

    for (int i = 1; i < numRows; i++) { // 앞에서 첫번째 라인 넣어줬으니 두번째 라인부터
        List<Integer> subList = new ArrayList<>();
        subList.add(1); // 어차피 첫번째 열은 1
        for (int j = 0; j < i - 1; j++) {
            int prevSubListIndex = i - 1;
            int firstAddingValue = ans.get(prevSubListIndex).get(j-1);
            int secondAddingValue = ans.get(prevSubListIndex).get(j);
            int sum = firstAddingValue + secondAddingValue;
            subList.add(sum);
        }
        subList.add(1);  // 어차피 마지막 열은 1
        ans.add(subList);
    }

    ans.forEach(s -> System.out.println(s.toString()));

    return ans;
}
⚠️ **GitHub.com Fallback** ⚠️