[python] Codility Lesson 9-2. MaxSliceSum

 

 

문제를 연습할 때, 바로 떠오르는 방법 먼저 시도해보고, 시간복잡도를 생각한 코드를 작성하고 있다.

 

맨 아래에 맨처음 2중 for문을 통해 풀어본 코드 (88%) 바로 아래 시간 복잡도를 고려한 코드를 첨부했다.

 

이번 문제는 뭔가 이전 문제와 크게 다르지 않은 것 같다.

 

음수관련 처리해주는데 생각이 복잡해져서 꽤나 애를 먹었다.

 

1. maxSum을 마이너스 끝판왕으로 설정해주고, sum을 0으로 초기값을 잡자.

 

2. for문을 돌면서 sum += a 해주자.

 

3. maxSum을 max(maxSum, sum)을 통해 갱신해주자

 

4. 여기서 조금 머리가 많이 아팠다 여러 예외 ( ex) 모두 마이너스일때, 섞여있을때, [3,-1,5]와 같은 경우 등.... ) 결국 sum이 음수만 아니면 sum을 갱신해줄 필요가 없다 (maxSum을 갱신해주기 때문에)

 

 

뭔가 저렇게 갱신해주고, max를 통해 갱신해주고 하는 유형이 꽤 보이는 듯 하다.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    maxSum = -float('inf')
    sum = 0
    for a in A:
        sum += a
        maxSum = max(maxSum, sum)
        sum = max(0, sum)
    return maxSum

 

 

* 아래 시간복잡도를 고려 안한 바로 작성해본 코드

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    sum = 0
    maxList = list()
    for i in range(len(A)):
        for j in range(i,len(A)):
            sum += A[j]
            maxList.append(sum)
        sum = 0
    return max(maxList)