[LeetCode] - 53. Maximum Subarray

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "Maximum Subarray" 문제입니다.

--> https://leetcode.com/problems/maximum-subarray/description/

 

문제 : 

Given an integer array nums, find the subarray with the largest sum, and return its sum.

---

Example 1 :

Input : nums = [-2,1,-3,4,-1,2,1,-5,4]

Output : 6

Explanation : The subarray [4,-1,2,1] has the largest sum 6.

 

Example 2 :

Input : nums = [1]

Output : 1

Explanation : The subarray [1] has the largest sum 1.

 

Example 3 :

Input : nums = [5,4,-1,7,8]

Output : 23

Explanation : The subarray [5,4,-1,7,8] has the largest sum 23.

 

Constraints :

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Follow up : If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

---

이 문제를 설명하자며는, 주어진 정수 배열에서 가장 큰 합을 가지는 부분 배열을 찾고, 그 합을 반환하는 문제입니다. 예를 들어, 입력이 [-2,1,-3,4,-1,2,1,-5,4]인 경우, 가장 큰 합을 가지는 부분 배열은 [4,-1,2,1]이며, 합은 6입니다. 사실 이 문제는 알고리즘 시간에서 어렴풋이 배운 거라 렉노 보면서 풀었습니다.

class Solution {
    public int maxSubArray(int[] nums) {
        return maxSubArrayRecursive(nums, 0, nums.length - 1);
    }

    private int maxSubArrayRecursive(int[] nums, int left, int right) {
        if (left == right) {
            // Base case: only one element
            return nums[left];
        }

        int mid = left + (right - left) / 2;

        // Maximum sum in the left half
        int maxLeftSum = maxSubArrayRecursive(nums, left, mid);

        // Maximum sum in the right half
        int maxRightSum = maxSubArrayRecursive(nums, mid + 1, right);

        // Maximum sum that crosses the mid
        int maxCrossSum = findMaxCrossingSum(nums, left, mid, right);

        // Return the maximum of the three sums
        return Math.max(Math.max(maxLeftSum, maxRightSum), maxCrossSum);
    }

    private int findMaxCrossingSum(int[] nums, int left, int mid, int right) {
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }

        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }

        return leftSum + rightSum;
    }
}

 

이 코드는 분할 정복(divide and conquer) 접근 방식을 사용하여 주어진 배열에서 최대 부분 배열 합을 찾습니다. 분할 정복 방식은 배열을 절반으로 나누어 각각의 부분 배열에서 최대 부분 배열 합을 찾고, 중앙을 기준으로 좌우 부분 배열을 합쳐서 최대 부분 배열 합을 계산합니다.

 

1. 재귀 함수 호출:
   • maxSubArrayRecursive 함수는 배열 nums를 좌우로 나누어 최대 부분 배열 합을 재귀적으로 계산합니다.
2. 분할 정복 접근법:
   • 배열을 중앙에서 나누고, 좌측과 우측 부분 배열에서 최대 부분 배열 합을 찾습니다.
   • 중앙을 기준으로 좌우 부분 배열을 합쳐서 최대 부분 배열 합을 찾습니다.
3. 중앙을 가로지르는 최대 부분 배열 합 계산:
   • 왼쪽 부분 배열에서 최대 합을 찾습니다.
   • 오른쪽 부분 배열에서 최대 합을 찾습니다.
   • 왼쪽과 오른쪽 부분 배열을 합쳐서 최대 합을 반환합니다.

시간 복잡도:

• 시간 복잡도: O(n log n)
  • 배열을 반으로 나누는 과정이 log n번 발생하고, 각 분할마다 O(n)의 시간이 소요됩니다. 따라서 전체 시간 복잡도는 O(n log n)입니다.
• 공간 복잡도: O(log n)
  • 재귀 호출의 깊이는 log n이므로, 호출 스택에 사용되는 공간 복잡도는 O(log n)입니다.

---

 

제 코드보다 더 잘 짜여지고 효율적이고 짧고 간결한 유저가 있길래 그분의 답안을 인용해 봤습니다.

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];

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

        return maxSum;
    }
}
// rahulvarma5297 유저의 코드

 

설명은 여기 이 분의 페이지를 보는 것을 추천드리겠습니다 : https://leetcode.com/problems/maximum-subarray/solutions/3666304/beats-100-c-java-python-beginner-friendly

 

---

코드 개선되기 전 후 Runtime 결과