숫자로 이루어진 리스트 nums를 인자로 주면, 그 안에서 어떤 연속적인 요소를 더했을 때 가장 큰 값이 나오나요? 가장 큰 값을 찾아 return해주세요.
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
- 설명: [4,-1,2,1] 를 더하면 6이 가장 크기 때문
앞에서부터 연속적으로 더한 값을 모두 저장하여 가장 큰 수를 반환
(사실 위의 방법은 이중반복문을 사용하기 때문에 비효율적이나, 다른 방법이 생각이 나지 않았다..ㅠㅠ)
def maxSubArray(nums):
output = [] (1)
for i in range(len(nums)):
sum = 0 (2)
for j in range(i,len(nums)):
sum += nums[j] (3)
output.append(sum) (4)
return max(output) (5)
(1) 모든 연속된 숫자의 합을 저장해줄 리스트 생성
(2) 첫번째 인덱스부터 연속된 숫자를 더해주며, 다음 인덱스의 연속된 숫자를 더하기 전 0으로 초기화
(3) 연속된 숫자의 합을 차례로 누적하며 구해줌
(4) (3)에서 구한 값을 output 리스트에 하나씩 추가
(5) 모든 경우의 수에서 가장 큰 값을 반환
→ 위의 방법은 비효율적인 방법이다. 추후 다른 풀이를 구하면 업데이트 해야겠다..