[LeetCode] 1800. Maximum Ascending Subarray Sum (Python)

Problem

Solution

sliding window

이전 문제와 유사하게 sub array 중 오름차순이면서 총 원소합의 최대값을 구하는 문제.

num array 가 100 이하라서 2중 포문을 사용해되지만 최대한 fot문을 1번만 사용하려고했다.

 

강력한 힌트는 The end of each ascending subarray will be the start of the next

subarray 만들고 체크한 마지막 인덱스가 다음 순회 인덱스의 첫번째 인덱스가 된다. 아래 코드에서 idx 가 그 역할.

 

아래는 더 깔끔한 코드가있어서 가져와봤다.

아예 처음부터 처음 0번째 값을 넣은 리스트를 선언 후 증가하는 값이 나올때마다 리스트에 추가 (cur list)

작아지는 숫자가 나오면 max 값 구하고 다시 cur list 초기화

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        result = 0
        cur = nums[0]

        for i in range(len(nums)-1):
            
            if nums[i] < nums[i+1]:
                cur += nums[i+1]
            else:
                result = max(cur, result)
                cur = nums[i+1]


        return max(cur, result)

Code

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        answer = 0
        idx = 0

        for i in range(1, len(nums)):
            print(i, idx)
            if nums[i-1] < nums[i]:
                if i == len(nums)-1:
                    tmp = nums[idx:]
                    subSum = sum(tmp)
                    answer = max(subSum, answer)
            else:
                tmp = nums[idx:i]
                subSum = sum(tmp)
                answer = max(answer, subSum)
                idx = i
                # print(tmp, subSum)
           
        # fully sorted increaasing array
        if answer == 0:
            answer = sum(nums)
        return answer

 

Complexity

Time Complexity

nums 길이만큼 순회했으므로 O(N)

 

Space Complexity

subSum, answer, idx 변수 사용 => O(1)

tmp 변수 사용 => O(N)

 

tmp 변수를 사용해서 O(N)의 공간복잡도가 나왔는데 아래와 같이 tmp에 저장하지 않고 단순 변수만 사용하면 O(1)로 줄일 수 있다.

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        answer = 0
        idx = 0
        for i in range(1, len(nums)):
            if nums[i-1] >= nums[i]:  # 비내림차순이면 새로운 구간 시작
                answer = max(answer, sum(nums[idx:i]))
                idx = i  
        answer = max(answer, sum(nums[idx:]))  # 마지막 구간 고려
        return answer