Leet Code - 53. Maximum Subarray(C++)

예제: 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.

풀이

최대 부분 수열 합을 구하는 문제이다.
문제 마지막에 보면, O(n) 시간내에 들어오도록 분할정복 방법을 써보라고 한다.
뭐.. 필자도 문제를 작게 나누어 재귀함수로 풀었으니 나름 분할정복이 맞지 않을까 싶다.
거기에다 익숙한 다이나믹 프로그래밍을 적용하였다.

소스코드를 보기 전에, 아주 단순하게 푼 아래의 풀이를 보자.

class Solution {
public:
	int maxSubArray(vector<int>& nums) {

		int maxNum = numeric_limits<int>::min();

		for (int i = 0; i < nums.size(); i++) {
			int sum = 0;
			for (int j = i; j < nums.size(); j++) {
				sum += nums[j];
				maxNum = max(maxNum, sum);
			}
		}

		return maxNum;
	}
};

2중 for문으로 간단하게 답을 구한건데, 심플하긴 하나 아래 서술할 동적 프로그래밍을 적용한 코드에 비해서 거의 100배까지도(...) 실행속도가 차이가 난다.

괜히 동적프로그래밍, 동적프로그래밍 하는게 아닌 것 같다.

다음은 전체적인 소스코드이다.

소스 코드

class Solution {
public:
	vector<int> cache;

	int maxNum(vector<int>& nums, int idx) {
		//base case
		if (idx == nums.size()) return 0;

		int& res = cache[idx];
		if (res != -1) return res;

		res = max(nums[idx], nums[idx] + maxNum(nums, idx + 1));

		return res;
	}

	int maxSubArray(vector<int>& nums) {

		//cache initialize;
		cache.resize(nums.size(), -1);
		maxNum(nums, 0);
		sort(cache.begin(), cache.end(), greater<int>());

		return cache[0];
	}
};

풀이 후기

총 3가지 방법으로 풀어보았는데, 런타임이 대부분 비슷하고, 그 근간은 모두 동적프로그래밍이므로 가장 짧은 코드를 올려보았다. 나머지 하나가 궁금하면 필자의 깃허브로..!!😁