[Python문제풀이-Dynamic Programming/Local MinMax] Maxslicesum

2025.03.15 - [프로그래밍/Python 관련 정보] - [Python] Table of Contents

---

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write function that given an array A consisting of N integers, returns the maximum sum of any slice of A.

유사 문제) 투자 귀재 규식이 1

https://www.codeit.kr/topics/practicing-algorithmic-problem-solving/lessons/1140?enrollWithStart=true

투자 귀재 규식이 I - 문제 해결 능력 기르기 | 코드잇

 

Brute Force로 풀어보기

잘못된 나의 풀이) idea 생성 후 곧바로 코딩으로 돌입하지 말고 다른 각도에서 좀 더 쉽게 접근할 수는 없을지 한 번쯤은 리뷰해보자. 

def sublist_max(profits):
    # 여기에 코드를 작성하세요
    ans_max = -10
    for i, v in enumerate(profits):
        for j in range(i)[::-1]:
            # tmp = sum(profits[j:i])
            ans_max = max(ans_max, sum(profits[j:i]))
    return ans_max

 

1) for j in range(i)[::-1]
이렇게 하면, i가 0일 때 아예 반복문이 돌지 않고, j가 항상 i-1에서 0까지 역순으로 순회. 실제로 우리가 보고 싶은 구간은 i부터 배열 끝까지

2) sum(profits[j:i])

아무리 Brute Force라지만 매번 sum을 다시하는 것은 비효율적

 

-------->
    <----

 

와 같은 "특이한" 방식으로 진행하면서 boundary에서 여러 리스크를 갖고 가는 것보다

좀 더 "일반적"인 방식을 고민

 

---->

---------->(끝)

 

def sublist_max(profits):
    ans_max = profits[0]

    for i in range(len(profits)):
        total = 0
        for j in range(i, len(profits)):
            total += profits[j]
            ans_max = max(ans_max, total)
    return ans_max

 

오답노트)

def solution(A):
    ans = - 2147483648
    temp = 0
    allneg = True
    negmaxi = - 2147483648
    for i in range(len(A)):
        if A[i]>=0:
            allneg = False
            temp += A[i]
            if i == len(A)-1:
                ans = max(ans, temp)
        else:
            ans = max(ans, temp)
            temp = 0
            negmaxi = max(negmaxi, A[i])
    if allneg:
        return negmaxi
    else:
        return ans

 

양수 뭉탱이들만 골라서 비교하면 된다고 생각했는데, 3, -2, 3처럼 음수가 끼어도 더 큰 양수가 있는 경우 차라리 더하는게 나은 케이스 존재

 

올바른 풀이1)

아래 블로그의 이미지를 참조합니다. https://sustainable-dev.tistory.com/23

https://sustainable-dev.tistory.com/23

 

def solution(A):

    dic = [0]*len(A)
    dic[0]=A[0]
    for i in range(1, len(A)):
        dic[i] = max(A[i], dic[i-1]+A[i])
        # if i ==1:
        #     print(dic[i])
    return max(dic)

 

 

올바른 풀이2)

def solution(A):
    # write your code in Python 3.6
    _max = A[0]
    _current = A[0]
    if current < 0:
        _current = 0

    for data in A[1:]:
        # add latest + current
        _next = _current + data
        # if two sum is larger than max, max = next
        if _next > _max:
            _max = _next
        # if two sum is larger than 0, current = next
        if _next > 0:
            _current = _next
        else:
            _current = 0

    # return max value
    return _max

 

 

---

왼쪽 그림과 같이 시작을 기준으로 생각하게 되면 일반항에서의 관계설정이 어렵습니다. 끝을 기준으로 부분최적구조를 생각하면 DP로 쉽게 접근이 가능하겠죠. 

대신 이렇게 설정한 a_n이 곧바로 문제의 답과 연결되지는 않아서 다시 한번 연산(max)를 취해주어야 하긴 합니다.

https://trillionver2.tistory.com/entry/Python%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Dynamic-Programming-%EC%A0%95%EC%88%98%EC%82%BC%EA%B0%81%ED%98%95

[Python문제풀이-DP/Local MinMax] 정수삼각형