アルゴリズム(Python)

ブリッジトラック

#다리를 지나는 트럭
def solution(length, weight, before_lst):
    ing_lst = [] # 다리를 지나고 있는 트럭
    ing_time = [] # 다리를 지나고 있는 트럭의 다리에 있었던 시간
    end_lst = [] # 다리를 지난 트럭
    n = len(before_lst)
    time = 0 # 시간
    while True:
        time += 1
        if ing_time:
            ing_time = [i+1 for i in ing_time] # 다리를 지나고 있는 트럭의 체류시간 +1
        if len(ing_lst) < length: # length 만큼 트럭이 머물 수 있다.
            if before_lst:
                i = before_lst[0]
                if sum(ing_lst)+ i <= weight: # 다리위트럭의 무게가 기준치를 안넘는다면 append
                    ing_lst.append(before_lst.pop(0))
                    ing_time.append(1)

        if ing_time[0] == length: # 다리위에 있는 트럭중 체류시간이 length 만큼 됐다면 pop
            ing_time.pop(0)
            end_lst.append(ing_lst.pop(0))
        if len(end_lst) == n:
            break
    return time+1

#다리를 지나는 트럭
def solution(length, weight, before_lst):
    ing_lst = []
    ing_time = []
    n = len(before_lst)
    time = 0
    cnt = 0
    while True:
        time += 1
        if ing_time:
            ing_time = [i+1 for i in ing_time]
        if len(ing_lst) < length:
            if before_lst:
                i = before_lst[0]
                if sum(ing_lst)+ i <= weight:
                    ing_lst.append(before_lst.pop(0))
                    ing_time.append(1)

        if ing_time[0] == length:
            ing_time.pop(0)
            ing_lst.pop(0)
            cnt += 1
        if cnt == n:
            break
    return time+1

れんけつ

1.初回アクセス

n = int(input())
queue = list(map(int, input().split()))
s = sum(queue)
cnt = 0
for i in queue:
    if i < 0:
        cnt += 1
if cnt == n: # 모든수가 음수일 때
    print(max(queue))

else:
    packet = []
    tmp = []
    v = queue.pop(0)
    vp = v>0
    tmp.append(v)
    while queue:
        vv = queue.pop(0)
        vvp = vv>0

        if vp == vvp:
            tmp.append(vv)
            v = vv
        else:
            packet.append(tmp)
            tmp = []
            # tmp.append(vv)
            v = vv
    packet.append(tmp)
    packet.append(queue)
    p = [sum(i) for i in packet]
    p.append(s)
    print(max(p))

2.完全ナビゲーションO(N^2)

n = int(input())
queue = list(map(int, input().split()))
result = []
for i in range(n):
    tmp = []
    tmp.append(queue[i])
    result.append(queue[i])
    for ii in range(i+1, n):
        tmp.append(queue[ii])
        result.append(sum(tmp))
print(max(result)) 

3.動的計画法

n = int(input())
nums = list(map(int, input().split())) # 입력 숫자
history = nums.copy() # 입력 숫자들을 더하는 기록 저장
max_val = -1000

for i in range(n):
    if i==0:
        continue
    if nums[i] < history[i-1] + nums[i]:
        history[i] = history[i-1] + nums[i]
    if history[i] > max_val:
        max_val = history[i]
print(max_val)

n = int(input())
nums = list(map(int, input().split())) # 입력 숫자
history = nums.copy() # 입력 숫자들을 더하는 기록 저장
max_val = nums[0]

for i in range(n):
    if i==0:
        continue
    if nums[i] < history[i-1] + nums[i]:
        history[i] = history[i-1] + nums[i]
    if history[i] > max_val:
        max_val = history[i]
print(max_val)