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

 

 

배열이 주어졌을때 합이 최대가 되는 연속된 부분의 합이 얼마인지 리턴하라는 문제

 

이런 경우에는 보통 Kadane`s Algorithm을 사용한다

이 알고리즘의 핵심 로직은 원소들이 양수인지 여부를 가리는데 있다.

만약 배열의 모든 원소가 양수라면 더할수록 최댓값을 경신 할 것이고,

음수라면 최대한 더하지 않는 것이(즉, 음수 중 최댓값을 갖는 원소 한개만) 최댓값일 것이다

 

 

Kadane`s Algorithm의 기본원리는 이전까지의 부분합 중 최대를 알아내는 것이다

이전까지의 부분합중 최대인 값을 알고 있다는 가정하에

현재 값이 양수라면 합했을때 최댓값을 경신하게 되고

현재 값이 음수라면 이전까지의 최댓값이 그냥 최댓값이 된다

 

그림을 기준으로 -1까지 더하는 경우에 대해 최댓값은 [4,-1]만 더한 경우일것이다

이전까지의 부분합 중 최댓값이 4이기 때문이다.

이렇게하면 각 index를 기준으로, 해당 원소가 포함된 부분합의 최댓값을 알 수 있다