[LeetCode] 53. Maximum Subarray

53. Maximum Subarray

LeetCode

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

Maximum Subarray - LeetCode

 

Given an integer array nums, find the subarray with the largest sum, and return its sum.

정수 배열 nums가 주어졌을 때, 합이 가장 큰 부분 배열(subarray)을 찾고 그 합을 반환하세요.

 

Example

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

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

---

1. 문제 요구사항 분석

합이 가장 큰 서브 배열 찾기

2. 접근 전략

😁 Dynamic Programming : i번째 원소를 반드시 포하하는 최대 부분 배열의 합

(공간복잡도 : O(n))

이전 합과 현재 합 비교해서 더 큰 값을 배열에 저장해두기

class Solution {
    public int maxSubArray(int[] nums) {
        int[] sum = new int[nums.length];

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

        return max;
    }
}

 

🤩 공간 복잡도 아끼는 방법 O(1)

카데인 알고리즘 (그리디 스타일)

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxi = Integer.MIN_VALUE;

        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            maxi = Math.max(sum,maxi);
            if (sum < 0){
                sum = 0;
            }
        }
        
        return maxi;

    }
}

카데인 알고리즘이란
과거가 짐이 된다면 버려라

 

카데인의 직관: "지금까지 더해온 결과가 총합 **음수(-)**라면, 이 뒤에 어떤 좋은 숫자가 나오든 간에 앞의 기록을 통째로 버리고 여기서부터 새로 시작하는 게 무조건 이득이다."