Leetcode – Maximum Ascending Subarray Sum Solution

Spread the love

The problem “Maximum Ascending Subarray Sum” is a classic array manipulation problem frequently encountered in coding interviews and competitive programming contests. It falls under the category of array and subarray problems and provides an excellent opportunity to learn how to traverse and manipulate array elements to extract valuable information. In this in-depth article, we will explore the problem statement, different approaches to solve it, their implementations in Python, and analyze their time and space complexities.

Problem Statement

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 [num[i], num[i + 1], ..., num[j]] of nums is ascending if num[i] < num[i + 1] < ... < num[j].

You can start and end the subarray at any index, but you must include at least one number in the subarray.

Examples

Input: nums = [10, 20, 30, 5, 10]
Output: 60

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

Approach 1: Simple Iteration

The most straightforward way to solve this problem is by iterating through the array while keeping track of the current subarray sum and the maximum subarray sum found so far.

Algorithm Steps

  1. Initialize variables current_sum and max_sum to 0.
  2. Loop through the array.
  3. Add the current element to current_sum.
  4. If the current element is less than or equal to the previous one, update max_sum and reset current_sum.
  5. Return max_sum.

Python Code

def maxAscendingSum(nums):
    current_sum = max_sum = 0
    for i in range(len(nums)):
        if i == 0 or nums[i] <= nums[i - 1]:
            current_sum = 0
        current_sum += nums[i]
        max_sum = max(max_sum, current_sum)
    return max_sum

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the array.
  • Space Complexity: O(1), as we are using only a few extra variables.

Approach 2: Using Enumerate

We can use Python’s enumerate function to simplify the code and make it more Pythonic.

Algorithm Steps

  1. Initialize variables current_sum and max_sum to 0.
  2. Loop through the array using enumerate.
  3. Add the current element to current_sum.
  4. If the current element is less than or equal to the previous one, update max_sum and reset current_sum.
  5. Return max_sum.

Python Code

def maxAscendingSum(nums):
    current_sum = max_sum = nums[0]
    for i, num in enumerate(nums[1:], 1):
        if num <= nums[i - 1]:
            current_sum = 0
        current_sum += num
        max_sum = max(max_sum, current_sum)
    return max_sum

Time and Space Complexity

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

Approach 3: Sliding Window (Optional)

Though the problem doesn’t require a sliding window approach due to its straightforward nature, it is instructive to see how it could fit into a sliding window paradigm, especially for those learning the technique.

Algorithm Steps

  1. Initialize variables current_sum, max_sum, start to 0.
  2. Loop through the array.
  3. Add the current element to current_sum.
  4. If the current element is less than or equal to the previous one, update max_sum and reset current_sum and start.
  5. Return max_sum.

Python Code

def maxAscendingSum(nums):
    current_sum = max_sum = start = 0
    for end in range(len(nums)):
        current_sum += nums[end]
        if end == 0 or nums[end] <= nums[end - 1]:
            current_sum = nums[end]
            start = end
        max_sum = max(max_sum, current_sum)
    return max_sum

Time and Space Complexity

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

Conclusion

The “Maximum Ascending Subarray Sum” problem is an excellent example of how to manipulate and traverse arrays to extract valuable information. The problem can be easily solved using simple iteration, but understanding its essence allows us to see how it can also fit into other algorithmic paradigms like the sliding window technique.

While all the approaches have similar time and space complexities, the choice of approach may depend on your familiarity and comfort with the programming constructs, like the enumerate function or the sliding window technique.

Leave a Reply