[Algorithm] 4주차 4번 문제

✅ 문제

---

숫자로 이루어진 리스트 nums를 인자로 받습니다.

그 안에서 어떤 연속적인 요소를 더했을 때 가장 큰 값이 나오나요? 가장 큰 값을 찾아 반환하는 프로그램을 작성해주세요.

예시)

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

설명)

[4,-1,2,1] 를 더하면 6이 가장 크기 때문

📌 풀이

---

첫번째 풀이 방법은 다음과 같습니다.

이중 for문을 사용하는 방법인데요.

#1 시작 위치는 첫번째 for문에서의 i의 값을 인덱스로 하는 값으로,

#2 끝나는 위치는 두번째 for문에서의 j+1의 값을 인덱스로 하는 값으로 배열을 인덱싱([:])합니다.

여기까지의 과정을 print()를 통해 출력을 해보면 다음과 같습니다:
예시는 문제의 예시를 사용하였습니다.

i=0, j=1(0+1) >> total_list = [-2]
i=0, j=2(1+1) >> total_list = [-2, -1]
i=0, j=3(2+1) >> total_list = [-2, -1, -4]
...

#3 인덱싱 한 값의 총 합을 구해 새로운 배열에 넣어주고, 그 배열에서 최댓값을 반환하는 방식입니다.

풀이로 알아보겠습니다.

def asnwer(nums):
	totla      = 0
    total_list = []
    
    for i in range(len(nums)):
    	for j in range(len(nums)):
        	`#1 ~ #2`
            total = sum(nums[i:j+1])
            total_list.append(total)
	`#3`
    result = max(total_result)
    
    return result

어쩔 수 없이 반복문을 여러개 사용해야하는 문제가 있을 수 있습니다.

문제에서 요구하는 값이 클 경우, 또는 반복문이 중첩이 아닌, 다른 반복문을 반드시 사용해야하는 경우 처리 속도 측면에서 굉장히 비효율적일 수 있습니다.

이번에는 반복문을 하나만 사용하면서, 배열의 값을 새로운 값으로 대입하여 풀어보겠습니다.

def answer(nums):
	total = 0
    
    for i in range(1, len(nums)):
		#1
		total = nums[i] + nums[i-1]
        
        #2
        nums[i] = max(nums[i], total)
    result = max(nums)
    
    return result

#1 반복문의 시작 index는 1입니다.
반복문을 순회하면서 처음 total 값은 이전 index와 합으로 업데이트됩니다.

#2 업데이트 되는 total은 현재 index를 지닌 값과 크기 비교를 통해 현재 index를 지닌 값에 다시 업데이트 됩니다.

이때 만약 현재 비교하는 값보다 total 값이 크다면 값은 업데이트되고 계속 누적이 될 것입니다.

각 과정을 출력해보면 다음과 같습니다.

i = 1 >> total = -1 >> [-2, 1, -3, 4, -1, 2, 1, -5, 4] 유지
i = 2 >> total = -2 >> [-2, 1, -2, 4, -1, 2, 1, -5, 4] 업데이트 (-3 → -2)
i = 3 >> total = 2  >> [-2, 1, -3, 4, -1, 2, 1, -5, 4] 유지
i = 4 >> total = 3  >> [-2, 1, -3, 4, 3, 2, 1, -5, 4] 업데이트 (-1 → 3)
i = 5 >> total = 5  >> [-2, 1, -3, 4, 3, 5, 1, -5, 4] 업데이트 (2 → 5)
i = 6 >> total = 6  >> [-2, 1, -3, 4, 3, 5, 6, -5, 4] 업데이트 (1 → 6)
i = 7 >> total = 1  >> [-2, 1, -3, 4, 3, 5, 6, 1, 4] 업데이트 (-5 → 1)
i = 8 >> total = 5  >> [-2, 1, -3, 4, 3, 5, 1, 1, 5] 업데이트 (4 → 5)