[LeetCode 53] Maximum Subarray with JAVA

leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

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

 

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 <= 3 * 104
• -105 <= nums[i] <= 105

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

1. 어려웠던 점:

- 카데인 알고리즘에 대해 이해하는데 오래 걸렸다.

특히, 내가 작성한 subMax에 해당하는 변수가 무엇을 의미하는지 깊게 생각해야했다.

 

2. 알게된 점:

 - 카데인 알고리즘

 

3. 알고리즘 풀이:

- ans는 현재까지의 최댓값을 나타낸다.

subMax는 해당하는 인덱스와 이전의 값들로 만든 부분배열들의 원소의 합 중 최댓값이다.

즉, subMax는 다음 인덱스에서 부분배열의 최대합을 구하는데 사용되지만, 이것이 ans를 보장한다고 할 수는 없다.

(해당 인덱스를 사용하지 않는 것이 더 큰 값일 수 있기 때문이다.)