[LeetCode/EASY] 53. Maximum Subarray (JAVA) : 문제&풀이

 

 

주어진 숫자 배열에 대한 서브 배열 중 합의 값이 가장 큰 서브 배열을 반환하는 문제이다.

예를 들어, {-2, 3, -1, 4}에서 합이 가장 큰 서브 배열은 {3, -1, 4}이다.

여기서 중요한 점은 서브 배열은 반드시 연속된다는 점이다.

({3, 4}와 같이 선택적 합은 불가능)

 

int 배열을 매개변수로 받는 maxSubArray 메서드의 틀이 주어진다.

 

Problem : 

public class MaximumSubarray {
    public int maxSubArray(int[] nums) {

    }
}

풀이는 주어진 maxSubArray 메서드에 작성하면 된다.

 

Solution :

1. 주어진 배열을 순서대로 돌며
   1. "현재 인덱스의 값"과 "지난 서브 배열 + 현재 인덱스의 값" 중 무엇이 더 큰지 비교한다.
   2. "1-1. 결과"와 "지금까지의 서브 배열 중 가장 큰 값" 중 무엇이 더 큰지 비교한다.
2. 배열을 다 돌고 난 후, 최종적으로 가장 큰 서브 배열의 합을 반환한다.

public class MaximumSubarray {

    // time complexity : for loop for given array -> O(n)
    // space complexity : just 2 variables regardless of the given array -> O(1)
    public int maxSubArray(int[] nums) {
        int currentSubarray = nums[0];
        int maxSubarray = nums[0];

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

        return max;
    }
}

 

이해하기 쉽게 그림으로 표현하면 다음과 같다.

 

 

Complexity :

• 시간복잡도 (Time Complexity)
  • 주어진 숫자 배열 길이에 따라 while문 반복하므로 O(n)
• 공간복잡도 (Space Complexity)
  • 주어지는 nums 배열의 크기와 상관없이 무조건 int 변수 2개만 사용하므로 O(1)

 

Sample(Test) :

public class MaximumSubarray {

    // time complexity : for loop for given array -> O(n)
    // space complexity : just 2 variables regardless of the given array -> O(1)
    public int maxSubArray(int[] nums) {
        int currentSubarray = nums[0];
        int maxSubarray = nums[0];

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

        return max;
    }

    public static void main(String[] agrs){
        int[] nums = {-2,3,-1,4};
        int[] nums1 = {2,1,-3,4,-1,2,1,-5,4};
        int[] nums2 = {1};
        int[] nums3 = {5,4,-1,7,8};

        MaximumSubarray m = new MaximumSubarray();
        System.out.println(m.maxSubArray(nums));
        System.out.println(m.maxSubArray(nums1));
        System.out.println(m.maxSubArray(nums2));
        System.out.println(m.maxSubArray(nums3));
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

6
6
1
23