1800.Maximum_Ascending_Subarray_Sum(Easy).md

1800. Maximum Ascending Subarray Sum (Medium)

Date and Time: Feb 4, 2025, 00:19 (EST)

Link: https://leetcode.com/problems/maximum-ascending-subarray-sum

Question:

Given an array of positive integers nums, return the maximum possible sum of an ascending subarray in nums.

A subarray is defined as a contiguous sequence of numbers in an array.

A subarray [nums_l, nums_l+1, ..., nums_r-1, nums_r] is ascending if for all i where l <= i < r, nums_i < nums_i+1. Note that a subarray of size 1 is ascending.

Example 1:

Input: nums = [10,20,30,5,10,50]

Output: 65

Explanation: [5,10,50] is the ascending subarray with the maximum sum of 65.

Example 2:

Input: nums = [10,20,30,40,50]

Output: 150

Explanation: [10,20,30,40,50] is the ascending subarray with the maximum sum of 150.

Example 3:

Input: nums = [12,17,15,13,10,11,12]

Output: 33

Explanation: [10,11,12] is the ascending subarray with the maximum sum of 33.

Edge Case:

Input: nums = [3,6,10,1,8,9,9,8,9]

Output: 19

Explanation: [9, 9] should reset curSum, because the second 9 is non-ascending.

Constraints:

• 1 <= nums.length <= 100

• 1 <= nums[i] <= 100

Walk-through:

Apply Kadane's Algorithm to use curSum, maxSum, prev to keep track and we update these three variables in every iteration. We need to check when there is the case that current element is non-ascending compare to the previous element nums[i] >= prev, if so, we reset curSum = 0.

Python Solution:

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        # set curSum, maxSum, prev to be the 1st element
        # If current > prev, curSum = 0. Else, increment curSum, update maxSum

        # TC: O(n), SC: O(1)
        curSum, maxSum, prev = nums[0], nums[0], nums[0]
        for i in range(1, len(nums)):
            # curSum = 0, when non-ascending element exists
            if nums[i] <= prev:
                curSum = 0
            curSum += nums[i]
            maxSum = max(maxSum, curSum)
            prev = nums[i]
        return maxSum

Time Complexity: $O(n)$
Space Complexity: $O(1)$