Maximum Subarray

🔗 문제 링크

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

🔍 문제 설명

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.

⚠️ 제한사항

• $1 <= nums.length <= 3 * 10^4$

• $-10^5 <= nums[i] <= 10^5$

🗝 풀이 (언어 : Java)

단순한 문제였지만 어려웠다. 어떤 것이 최대값을 구하는 방법인지 생각해봐도 헷갈렸다. 정답 알고리즘을 보면 부분적 집합들의 최대값을 구하는 변수가 있고, 이 변수 값들 중에 최대값을 구하는 변수를 선언한다. 부분적인 누적합을 구할 때, 앞에서 -가 나오면 버리고 해당 인덱스 값부터 다시 누적을 시작한다. 매번 부분 누적합을 전체 최대값과 비교하여 갱신한다.

class Solution {
    public int maxSubArray(int[] nums) {
        int curMax = nums[0], allMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 부분 누적 최대값, 현재 1개짜리 원소로 다시 시작할지, 누적값으로 계속갈지 더 큰값으로 정하는 기능도 한다
            curMax = Math.max(nums[i], curMax+nums[i]);
            // 전체 최대 값
            allMax = Math.max(allMax, curMax);
        }
        return allMax;
    }
}