[LeetCode] 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.

Example:

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

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 

Approach

nums[i]까지 다 더했을때의 결과를 저장하는 array를 하나 만들고

이 더한 값들의 결과를 저장한 array를 사용해 숫자를 연속해서 2개 더했을 때 결과, 3개 더했을 때 결과, ..., N개 더했을 때 결과를 비교해 가장 큰 수를 리턴한다.

시간복잡도는 O(n^2) 엄청느림

 

Optimization

위의 방법은 너무 비효율적이다.

포인트는 앞에서부터 숫자들을 더하되 다 더해진 숫자가 음수가 되면 여기에서 끊고 다음 숫자부터 다시 연속해서 더하는 것.

이는 말보다 코드를 통해 더 설명하기가 쉽다.

 

Code

Slow: https://github.com/chi3236/algorithm/blob/master/LeetCode_MaximumSubarray_Slow.cpp

chi3236/algorithm

Optimized: https://github.com/chi3236/algorithm/blob/master/LeetCode_MaximumSubarray_Optimized.cpp

chi3236/algorithm