[LeetCode] Maximum Subarray | 난이도: Easy

문제

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.

 

주어진 배열의 부분 배열(subarray)의 합 중 최대값을 구하시오.

부분 매열은 연속적인(contiguous) 배열이어야 한다.

[1,2,3,4] 배열을 예시로 들자면, [1,2]는 부분배열로 가능하지만, [1,3]또는 [1,4]와 같이 연속적이지 않고 서로 떨어져 있는 값들은 조건에 어긋난다.

---

예시

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

---

답안_Brute Force

class Solution {
    public int maxSubArray(int[] nums) {
        
        int currSum = nums[0];
        int maxSum = currSum;
        
        for(int i = 0; i < nums.length; i++){
            currSum = nums[i];
            if(currSum > maxSum) maxSum = currSum;
            for(int j = i+1; j<nums.length; j++){
                currSum = currSum + nums[j];
                if(currSum > maxSum) maxSum = currSum;
            }
        }
        return maxSum;
    }
}

currSum : 현재 subarray의 합계. 첫번째 인덱스를 default 값으로 한다.

maxSum : 궁극적으로 구하고자 하는 결과값.

배열을 두 번 돌면서 해당 인덱스 i가 가질 수 있는 모든 부분 배열의 합을 구한다.

 

답안_Kadane's Algorithm

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

---

참고

https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d

Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?

https://sustainable-dev.tistory.com/23

Dynamic Programming - Kadane’s Algorithm (카데인 알고리즘)