[LeetCode] 53. Maximum Subarray - 문제풀이

Description

주어진 배열(nums)의 subarray중 가장 큰 인접한 수를 갖는 배열을 찾아서 값을 반환하는 문제입니다.

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 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.

Solution 1. 전체 탐색(brute force)

public int maxSubArray2(int[] nums) {
    // 1. brute force
    int len = nums.length;
    int max = nums[0];
    for(int i=0; i<len; i++){
        int localMax = nums[i];
        int sum = 0;
        for(int j=i; j<len; j++){
            sum += nums[j];
            localMax = Math.max(localMax,sum);  //i 요소로 시작하는 최대 부분합
        }
        max = Math.max(max,localMax); // 각 인덱스 최대부분합 중 최대값
    }
    return max;
}

가능한 모든 경우의 수를 전체 탐색하는 방법입니다. 주어진 요소별로 이중 반복문을 통해 순회하며 인덱스(i) 하나하나의 최대값을 구하고 다시 각 인덱스의 최대 값중 큰값을 반환해 줍니다.

시간 복잡도가 높아 Time Limit Exeeded 가 발생합니다.

• 시간 복잡도 : O(N^2)
• 공간 복잡도 : O(1)

출처-https://sustainable-dev.tistory.com/23

Solution 2. 카데인 알고리즘(Kadane's Algorithm)

public int maxSubArray(int[] nums) {
        
    int len = nums.length;
    int max = nums[0];
    int localMax = nums[0];
    for(int i=1; i < len; i++){
        localMax = Math.max(localMax+nums[i],nums[i]);   //현재 index에서의 가장 큰 값
        max = Math.max(localMax,max); // 각 인덱스의 최대값들 중에 가장 큰 값
    }
    return max;
}

다이나믹 프로그래밍(Dynamic Programming)의 방식을 적용한 카데인 알고리즘을 이용해서 O(N)의 복잡도로 쉽게 풀어낼 수 있습니다. 이전 인덱스(i-1)의 부분집합 까지의 최대 합과 현재 인덱스(i)의 최대 합은 현재 요소(i)의 값이거나 이전 부분집합의 최대 값+ 현재 요소 둘 중 하나입니다.

이런식으로 이전에 계산했던 최대값을 분할 하여 재활용 해나가는 방법입니다.

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(1)

출처-https://sustainable-dev.tistory.com/23

Reference

Maximum Subarray - LeetCode