[알고리즘] 정수 배열(int array)가 주어질 때 가장 큰 이어지는 원소들의 합을 구하기, Brute force, python(4)

정수 배열(int array)가 주어질 때 가장 큰 이어지는 원정수 배열(int array)가 주어질 때 가장 큰 이어지는 원소들의 합을 구하기.

가령 예를 들면

 

input : [7, -3, 4, -8]

[7, -3, 4] 구간이 가장 합이 크므로 8을 return

 

input : [-2, -3, 4, -1, -2, 1, 5, -3]

[4, -1, -2, 1, 5] 구간이 가장 합이 크므로 7을 return

key point :  이어지는 배열이 가장 커야 한다. 

 

Brute force 방식을 이용하면 그렇게 어렵지 않다.

 

# brute force 방법을 사용한다. 
def sum_max_period(profits):
    sum_final = []
    #결과값을 담을 list
    
    for i in range(len(profits)):
        sum_max = 0
        #i가 iteration이 될 때마다 sum_max는 reset된다. 
        
        for j in range(i, len(profits)):
            #0번 index부터 ~list의 끝까지 차례대로 더한 값을 더한다. 
            #1번 index부터 ~list의 끝까지 차례대로 더한 값을 더한다. 
            #반복
            
            sum_max+=profits[j]
            sum_final.append(sum_max)
            
    return max(sum_final)
    #최대값을 return