2JINISHAPPY 2JINISHAPPY

Maximum subarray problem이라는 문제가 있다 N개의 원소를 가진 배열이 있을 때, (i,j)의 연속되는 인덱스를 선택했을 때의 원소 최대 합을 구하는 문제이다 즉 [4, -2, 5, -4, 3, -7, -6, 10, 5]라는 배열이 있을 때 maximum subarray problem의 답은 7~8번째 원소값을 더한 15가 된다. 이 때 가능한 해결법은 약 세가지가 있다 1️⃣ 모든 인덱스 (i, j)에 대해 sum을 계산한 뒤 maximum값을 구한다 for(int i=0;i maxSum)maxSum = sum; } } 구간합을 구하기 위해 앞에서 구한 값을 활용해줬다. (i,j)의 구간 합 = (i,j-1)의 구간 합 + (j)의 원소 값인 점을 이용한다. 하지만 이 경우에도 시간복..