[Leetcode] Maximum Subarray

https://github.com/lkimilhol/studyForCodingTest/blob/master/src/com/company/Leetcode/MaximumSubArray.java

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

---

배열 하나가 주어지면 그 안에서 최대 합이 되는 부분 배열을 구하는 문제입니다.
배열 [-2,1,-3,4,-1,2,1,-5,4]가 주어진다면 답은 [4,-1,2,1]의 합인 6이 되는 것입니다.

문제는 쉽지만 처음 이런 문제를 접하게 되면 순간적으로 좀 당황하게 됩니다. 또한 O(N^2)으로도 문제를 풀 수 있겠지만 시간이 오래 걸려 좋은 점수를 받지 못할 것입니다.

배열에서 부분합이 음수가 되는 부분은 사실 고려하지 않아도 될 것입니다. 왜냐하면 최대합에 음수를 더하면 당연히 최대합에서 그 음수만큼 작은 숫자가 되기 때문입니다.

따라서 우리는 부분 배열이 양수인 것만 더해주고, 이 값이 최대합보다 크다면 그 최대합을 바꿔주면 됩니다.

생각보다 쉬운 문제입니다.

public class MaximumSubArray {
    public static int solution(int[] nums) {
        int total = nums[0];
        int subSum = 0;
        for (int num : nums) {
            subSum += num;
            total = Math.max(subSum, total);
            if (subSum < 0)
                subSum = 0;
        }

        return total;
    }
}