[array] maximum subarray

✅ Problem

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

 

✅ Approach & Solution

방식) 시간복잡도 : O(n)

• 부분집합의 합이 양수일 때 : 해당 부분집합 유지
• 부분집합의 합이 음수일 때 : 새로운 부분집합으로 시작

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

        for (int num : nums) {
            currentSum += num;

            maxSum = Math.max(maxSum, currentSum);

            if (currentSum < 0) {
                currentSum = 0; // 새로운 부분집합으로 시작
            }
        }

        return maxSum;
    }
}

 

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

        for (int num : nums) {
            currentSum = Math.max(num, currentSum + num); // num > currentSum + num 일 때 새로운 부분집합으로 시작
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}