LSCS 구하기
LSCS는 Largest Sum of Contiguous Subarray의 약자로, 연속된 부분배열의 합들 중 가장 큰 합을 의미합니다. 연속된 부분 배열이란 예를 들어서 전체 배열이 {1, 2, 3} 인 경우에 {1}, {1,2}, {1,2,3}, {2}, {2,3}, {3} 과 같이 인접한 원소들로만 이루어진 집합을 의미합니다. 이 배열의 LSCS는 부분배열 {1,2,3}의 원소의 합인 6이 됩니다. 원소들이 0이상의 정수라면 단순히 모든 원소를 다 더하면 LSCS가 되겠지만, 음수가 포함되는 경우는 조금 다른 결과가 나올 것입니다. 위의 문제를 만났을 때 배열의 index를 포인터 삼아 포인터를 옮겨가며 모든 부분배열 원소의 합을 각자 구한 뒤, 그 중에서 가장 큰 값을 구하는 방법을 사용했습니다...
2022. 7. 28.