Code Implementation

class Solution:
    def maxAscendingSum(self, nums):
        max_sum = curr_sum = nums[0]
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                curr_sum += nums[i]
            else:
                curr_sum = nums[i]
            max_sum = max(max_sum, curr_sum)
        return max_sum
      

class Solution {
public:
    int maxAscendingSum(vector<int>& nums) {
        int maxSum = nums[0], currSum = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i - 1]) {
                currSum += nums[i];
            } else {
                currSum = nums[i];
            }
            maxSum = max(maxSum, currSum);
        }
        return maxSum;
    }
};
      

class Solution {
    public int maxAscendingSum(int[] nums) {
        int maxSum = nums[0], currSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                currSum += nums[i];
            } else {
                currSum = nums[i];
            }
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }
}
      

var maxAscendingSum = function(nums) {
    let maxSum = nums[0], currSum = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            currSum += nums[i];
        } else {
            currSum = nums[i];
        }
        maxSum = Math.max(maxSum, currSum);
    }
    return maxSum;
};
      

Problem Description

You are given an array of positive integers called nums. An ascending subarray is a contiguous part of nums where each element is strictly greater than the previous one. The task is to find the subarray (of any length) with the largest possible sum, where the subarray is strictly ascending. Return this maximum sum as an integer.

• Each subarray must be contiguous (no skipping elements).
• Each number can only be used once per subarray.
• There is always at least one valid subarray (even a single number).

Thought Process

To solve this problem, we first consider the brute-force approach: checking every possible subarray, summing those that are strictly ascending, and keeping track of the maximum sum found. However, this would be inefficient for large arrays, as it examines all possible subarrays.

Instead, we can optimize by recognizing that we only care about contiguous segments where the sequence is strictly increasing. As we scan through the array, we can build up the sum of the current ascending subarray, resetting it whenever the sequence is broken (i.e., when the next number is not greater than the previous). This way, we only need a single pass through the array.

Solution Approach

• Initialize: Set two variables: max_sum and current_sum, both starting at the first element of nums.
• Iterate: Loop through nums starting from the second element.
  • If the current number is greater than the previous one, add it to current_sum (continue the ascending subarray).
  • If not, reset current_sum to the current number (start a new potential ascending subarray).
• Update Maximum: After each step, update max_sum if current_sum is greater.
• Result: After the loop, max_sum holds the answer.

This approach is efficient because it processes each number only once, and always keeps track of the best sum found so far.

Example Walkthrough

Let's walk through an example with nums = [10, 20, 30, 5, 10, 50].

1. Start with max_sum = current_sum = 10.
2. 20 > 10: Add to current_sum (now 30). max_sum = 30.
3. 30 > 20: Add to current_sum (now 60). max_sum = 60.
4. 5 < 30: Reset current_sum to 5. max_sum remains 60.
5. 10 > 5: Add to current_sum (now 15). max_sum remains 60.
6. 50 > 10: Add to current_sum (now 65). max_sum = 65.

Final answer: 65, which is the sum of the subarray [5, 10, 50].

Time and Space Complexity

• Brute-force approach: O(n²) time, since we would check all possible subarrays, and O(1) space.
• Optimized approach (current solution): O(n) time, because we process each element once, and O(1) space, since we only use a few variables.

The optimized approach is much better for large arrays, as it avoids redundant work and uses minimal memory.

Summary

The key insight is that we can efficiently find the maximum ascending subarray sum by scanning the array once, maintaining a running sum for each ascending segment, and updating the maximum as we go. This avoids the inefficiency of checking all subarrays and makes the solution both simple and fast.