LeetCode 53(Maximum Subarray, java)

0. 문제

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

Maximum Subarray - LeetCode

 

1. 문제 설명

- 위의 문제의 핵심은 연속적인 배열 요소의 합 중에서 가장 큰 값을 찾는 것이다.

- 이 문제에서 생각해야 할 것은 어떻게 연속적인 배열의 시작 요소를 어떻게 찾을 것이냐는 것이다.

 

- 다음 예시를 보자.

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

 

- 위의 배열은 매개변수로, 문제에서 주어지는 배열이다.

 

- 연속적인 배열의 시작 요소를 찾는 방법은 다음과 같다.

 

  → 변수를 만들어 첫번째 요소(= -2)로 초기화한다. 

  → 그리고 현재 가리키는 요소를 두 번째 요소(= 1)로 설정한다.

  → 첫 번째 요소(= -2)와 두 번째 요소의 합을 구하면 -1이다.

  → 두 요소의 합이 -1이지만 두 번째 요소가 1이므로 더 크다.

  → 최대 합을 구하기 위해서는 덧셈을 할 수록 값이 커져야한다.

  → 그러므로 첫 번째 요소(= -2)는 연속적인 배열의 최대 합을 구하기 위한 시작 요소로 부적절하다.

   

- 이와 같은 검증을 반복하여 적절한 시작 요소를 찾고 최대 합을 구한다.

- 적절한 시작 요소가 1개라는 보장은 없기 때문에, 매번 덧셈의 결과를 비교하여 더 큰 값을 최대 합으로 저장한다.

 

2. 해답 코드

class Solution {
   public int maxSubArray(int[] nums) {
      int curn = nums[0];
      int result = nums[0];
      
      for(int i = 0; i < nums.length; i++) {
         int temp = curn + nums[i];
         curn = Math.max(temp, nums[i]);
         result = Math.max(result, curn);
      }
      return result;
   }
}