[-2,1,-3,4,-1,2,1,-5,4]와 같은 vector가 주어지면, 그 안에서 연속된 숫자열의 합 중 가장 큰 것을 return하는 문제이다.

[4,-1,2,1]의 경우가 가장 큰 합을 낼 수 있으므로, return은 그 합인 6을 보내면 된다.


int maxSubArray(vector& nums)
{
	if (nums.size() <= 0)
		return 0;

	int nRet = 0x80000000;

	for (int i = 0; i < nums.size(); ++i)
	{
		int nTempSum = nums[i];
		for (int j = i + 1; j < nums.size(); ++j)
		{
			if (nTempSum > nRet)
				nRet = nTempSum;
			nTempSum += nums[j];
		}
		if (nTempSum > nRet)
			nRet = nTempSum;
	}

	return nRet;
}


성능이 좋은 편은 아닌데, 어차피 로직 자체는 성능이 좋으나 그렇지 않으나 거의 비슷비슷하다

저작자 표시 비영리 변경 금지
신고

'Programming > C/C++' 카테고리의 다른 글

[LeetCode] 58. Length of Last Word  (0) 18:29:44
[LeetCode] 53. Maximum Subarray  (0) 18:10:29
[LeetCode] 617. Merge Two Binary Trees  (0) 2017.11.07
[LeetCode] 498. Diagonal Traverse  (0) 2017.11.06
[LeetCode]342. Power of Four  (0) 2017.11.06
[LeetCode]Reverse Integer2  (0) 2017.11.06
by 가우초 2017.11.21 18:10