[Algospot] FENCE

책 풀이

import sys

testcase = int(sys.stdin.readline())
ans = []

for t in range(testcase):
    N = int(sys.stdin.readline())
    fence = list(map(int,sys.stdin.readline().split(" ")))

    def div_conq(left,right):
        if (left == right):
            return fence[left]
        mid = (left+right)//2

        ret = max(div_conq(left,mid),div_conq(mid+1,right))

        low = mid
        high = mid+1
        height = min(fence[low],fence[high])
        area = height*2

        while(left<low or high < right):
            if (high<right and (low ==left or fence[low-1]<fence[high+1] )):
                high+=1
                height = min(height,fence[high])
            else:
                low-=1
                height = min(height,fence[low])
            
            area = max(area,height*(high-low + 1))
        return max(ret,area)
        

        
    print(div_conq(0,N-1))

실패한 풀이,,

import sys

testcase = int(sys.stdin.readline())
for t in range(testcase):
    N = int(sys.stdin.readline())
    fence = list(map(int,sys.stdin.readline().split()))

    def dfs(target,index,dir):
        if index < 0 or index >= N:
            return 0
        if fence[index] < target :
            return 0

        return target+dfs(target,index+dir,dir)
        
    ans = 0
    for i in range(N):
        left = dfs(fence[i],i,-1)
        right = dfs(fence[i],i+1,1)
        ans = max(ans,left+right)
    
    print(ans)