[CodeKata] 15. maxSubArray

그냥·2022년 6월 30일
0

CodeKata

목록 보기
16/18

문제

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

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


풀이


1. 문제의 조건 정리
1) 숫자로 이루어진 배열을 인자로 받음
2) 연속되는 요소의 합 중 가장 큰 정수 값을 반환함

2. 조건에 대한 코드 구현 방법 생각
1) 이중 for문을 사용해서 모든 연속되는 요소의 합을 구한다.
2) 합을 리스트에 추가한다.
3) 가장 큰 값을 반환한다.

3. 구현 코드
def maxSubArray(nums):
  result = []

  if len(nums) == 1:
    return nums[0]
  
  for i in range(len(nums)):
    for j in range(len(nums)):
      if i > j:
        continue
      else:
        result.append(sum(nums[i:j+1]))
  return max(result)

4. 코드 리뷰
1) nums의 요소가 1개인 경우는 이중 for문 내에서 해결 할 수 없어서 if문에서 미리 제거함
-> 하드 코딩이라 좋은 방법은 아님
2) 이중 for문으로 모든 배열의 요소를 하나씩 다 더 하는 방법은 너무 비효율적임

0개의 댓글