[LeetCode] 53. Maximum Subarray (C++)

문제

 

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

Maximum Subarray - LeetCode

 

풀이

 

난이도: Easy

 

부분배열[start, end]의 시작을 start, 끝을 end라고 하자. 

end를 +1씩 증가시켜 원소를 하나씩 부분 배열에 추가시킬때 사실 end가 음수의 값이더라도,

부분배열의 합(sum)이 여전히 양수라면 해당 음수는 부분 배열에 추가시켜 이어나갈 가치가 있다.

하지만 해당 음수가 추가되어 sum이 음수가 된다면 더 이상 [start, end]의 부분 배열은 이어나갈 팔요가 없다.

따라서 sum이 음수일때는 sum은 0으로 초기화 시켜주자.

이는 end의 다음 수부터 새로운 부분 배열을 시작한다는 의미와 같다.

 

배열을 한번만 순회해도 최대 부분 배열을 구할 수 있으므로 시간 복잡도는 O(n) 이다.

 

코드

	class Solution {
	public:
	int maxSubArray(vector<int>& nums) {
	int sum =0, max_sum = nums[0];
	for (int idx =0; idx< nums.size(); ++idx) {
	sum += nums[idx];
	max_sum = max(max_sum, sum);
	if (sum < 0)
	sum = 0;
	}
	return max_sum;
	}
	};

view raw Maximum Subarray.cpp hosted with ❤ by GitHub