[Python] Code Kata Day19

문제

숫자로 이루어진 리스트 nums를 인자로 주면,
그 안에서 어떤 연속적인 요소를 더했을 때 가장 큰 값이 나오나요?
가장 큰 값을 찾아 return해주세요.

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
설명: [4,-1,2,1] 를 더하면 6이 가장 크기 때문

내코드

def maxSubArray(nums):
  idx = []
  sums = []
  for i in range(len(nums)):
    if nums[i] > 0:
      idx.append(i)
  if len(idx) == 0:
    return 0
  elif len(idx) == 1:
    return (nums[idx[0]])
  else:
    for i in range(len(idx)):
      start = idx[i]
      for j in range(i+1, len(idx)):
        end = idx[j]
        sums.append(sum(nums[start:end+1]))
    return max(sums)

일단 생각나는대로 작성했는데, 만약 최대값이 되려면 시작과 끝은 양수가 되어야된다고 생각했고 양수의 모든 인덱스를 찾아서 idx에 append한 후에 해당 인덱스들의 사이에 있는 값들을 더할 수 있는 모든 경우를 찾아서 더한 값을 sums 리스트에 저장한 후 나중에 최댓값을 뽑아냈다. 가장 바깥쪽 조건문은 테스트를 돌리다가 부랴부랴 집어넣었다. 썩 깨끗한 답은 아닌 것 같다.

Model Solution

def maxSubArray(nums):
  for i in range(1, len(nums)):
    if nums[i-1] > 0:
      nums[i] += nums[i-1]
      
  print(nums)
  return max(nums)
  
maxSubArray([-2,1, 3, 4, -3, 3])

중간에 합이 음수로 바뀌지 않는 이상 계속 더해나간다.

만약 [-2, 1, -3, 4, -1, 2, 1, -5, 4]면 for문을 돌린 후에는 [-2, 1, -2, 4, 3, 5, 6, 1, 5]로 바뀐다. 각 요소가 합으로 대체되므로 합이 계속 기록되고 그 중 가장 최댓값을 찾으면 된다.