Codility - MaxDoubleSliceSum 문제풀이

생각이 잘 안나서,

구글링 했다.

 

시간 복잡도: O(N) --> 100%의 정답률

# 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
    
    l_max_slice_sum = [0]*len(A)
    r_max_slice_sum = [0]*len(A)
    
    for i in range(1,len(A)-2):
        l_max_slice_sum[i] = max(l_max_slice_sum[i-1]+A[i],0)
    
    for i in range(len(A)-2,1,-1):
        r_max_slice_sum[i] = max(r_max_slice_sum[i+1]+A[i],0)
            
    max_slice_sum = l_max_slice_sum[0] + r_max_slice_sum[2]
    
    for i in range(1,len(A)-1):
        max_slice_sum = max(max_slice_sum,l_max_slice_sum[i-1]+r_max_slice_sum[i+1])
    
    return max_slice_sum
    pass

 

아래는 위 코드 참고해서 내가 짠 코드!!

# 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
    
    
    #A
    #[0][1][2][3][4][5][6][7]
    # 3  2  6 -1  4  5 -1  2
    
    #A = [6, 1, 5, 6, 4, 2, 9, 4]
    
    front_sum = [0]*len(A)
    back_sum = [0]*len(A)
     
    for i in range(1,len(A)-2):
        if front_sum[i-1]+A[i] > 0:
            front_sum[i] = front_sum[i-1]+A[i]
            
            
            
        
    for i in range(len(A)-2,1,-1):
        if back_sum[i+1]+A[i] > 0:
            back_sum[i] = back_sum[i+1]+A[i]
            
    
    max_sum = 0
    
    for i in range(0,len(A)-2):
        if front_sum[i] + back_sum[i+2] > max_sum:
            max_sum = front_sum[i] + back_sum[i+2]
    
    
    return max_sum
    
    pass

 

 

첫번째 코드는 아래의 사이트 참고했다.

 

https://curt-park.github.io/2018-09-14/algorithm-max-double-slice-sum/

[Algorithms] MaxDoubleSliceSum