LSCS

Largest Sum of contiguous Subarray

정수 배열의 연속 부분 배열의 합 중 최댓값 구하기

public class Solution { 
	public int LSCS(int[] arr) {
        for(int i=0; i<arr.length; i++){
          temp+=arr[i];
          if(temp>LS) LS=temp;
          if(temp<0) temp=0;
        }
    return LS;
	}
}

연속된 값을 계속해서 더해가며 최댓값을 저장하는데, 만약 합이 음수가 나오면 다시 새로 시작하여 검사를 반복한다.

합이 음수가 나오면 이전까지 구했던 최댓값에서 그 뒤에 음수나 양수나 수가 나오면 그전의 합인 음수를 더하지 않는 것이 더 크기 때문에 그 전까지 더한 음수 값을 버리고 다시 시작한다.