[LeetCode] 53. Maximum Subarray

Problem

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

---

Solution

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum < 0)
                sum = nums[i];
            else
                sum += nums[i];
            if (max < sum)
                max = sum;
        } return max;
    }
}

Explanation

• 배열 nums내에, 여러 Subarray속 요소들의 합계 중 가장 큰 합계를 나타내기 위한 변수 max를 선언한다.
• 변수 max를 초기화 해줘야 하는데, 배열 nums속 Subarray의 가장 큰 합계가 정수형의 마이너스 범위(-2^31)를 넘어서는 경우를 대비해 Integer.MIN_VALUE로 초기화해준다.

  int max = Integer.MIN_VALUE;
  

• 문제에서 배열 속 요소들의 합을 요구하고 있으므로, 이 합계를 나타내기 위한 변수 sum과 배열의 합을 구할 for 반복문을 작성한다.

  int sum = 0;
  for (int i = 0; i < nums.length; i++) {
    sum += nums[i];
  

• 변수 sum의 값이 Integer.MIN_VALUE로 초기화된 변수 max의 값보다 크면 변수 max값에 변수 sum의 값을 할당하도록 위의 for 반복문속에if 조건문을 작성한다.

  if (max < sum)
    max = sum;
  

• for 반복문을 진행하면서, Subarray가 뒤로 점점 길어질 수는 있지만, 새로운 요소로 시작하는 Subarray를 만들 수는 없다.
• 그리고 Subarray속 요소들의 합이 0보다 작아지는 순간, 그 Subarray는 변수 max의 값을 작아지게 만드므로, 계산에 필요 없는 Subarray가 된다. 이를 해결하기 위해 if 조건문을 추가하여 새로운 요소로 시작하는 Subarray를 만들 수 있도록 한다.

  if (sum < 0)
    sum = nums[i];
  else
    sum += nums[i];
  

• 변수 max의 값을 반환한다.

  return max;