Maximum Subarray

부분 배열은 간격 없이 이어진 리스트 요소들의 연속 구간입니다. 정수 리스트의 비어 있지 않은 모든 부분 배열 중 요소의 합이 가장 큰 부분 배열을 찾고, 그 합을 반환합니다.

[2, -4, 3, -1, 5, -6, 1]에서는 [3, -1, 5]가 가장 좋은 연속 구간이며, 합은 7입니다. 뒤에 오는 5가 -1의 손실을 충분히 만회하므로 -1을 포함하고, 뒤따르는 -4의 손실이 앞의 2가 더하는 값보다 크므로 맨 앞의 2는 제외합니다.

한 번 순회하는 고전적인 해법은 Kadane 알고리즘입니다. 리스트를 순회하면서 현재 요소에서 끝나는 연속 구간의 합 중 최댓값을 유지합니다. 각 요소에서 선택지는 두 가지뿐입니다. 이전 요소에서 끝난 연속 구간을 확장하거나, 여기서 시작하는 새 연속 구간으로 다시 시작하는 것입니다. 이전 연속 구간의 합이 양수일 때만 확장이 이득입니다. 그 합이 0 이하로 떨어지면 계속 포함해도 손해만 되므로 새로 시작합니다. 답은 순회하는 동안 발견한 연속 구간 합 중 최댓값입니다.

예시에서 각 위치에서 끝나는 최선의 연속 구간 합은 2, -2, 3, 2, 7, 1, 2이므로 답은 7입니다. 각 요소를 한 번씩만 확인하므로 리스트의 길이에 비례해 작업량이 증가합니다.

maxSubArray라는 이름의 함수를 작성하세요. 이 함수는 정수 목록 nums를 입력받아 nums의 비어 있지 않은 연속 부분 배열의 합 중 가장 큰 값을 반환해야 합니다.

제약 조건: 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4.