algoadvance

Leetcode 1800. Maximum Ascending Subarray Sum

Problem Statement

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

• A subarray is a contiguous sequence of elements within an array.
• An ascending subarray is a subarray where each element is strictly greater than the preceding one.

Example

Input: nums = [10, 20, 30, 5, 10, 50]
Output: 65
Explanation: [10, 20, 30] is the ascending subarray with the maximum sum.

Clarifying Questions

1. Can the array be empty?
   • No, the array will have at least one element.
2. What are the constraints on the elements in the array?
   • The elements are positive integers.
   • The length of the array is between 1 and 1000.

Strategy

1. Traverse through the array while maintaining the sum of the current ascending subarray.
2. If the current element is greater than the previous element, add it to the current sum.
3. If not, then compare the current sum with a running maximum sum and update the maximum sum if necessary. Reset the current sum to the current element.
4. Ensure to do a final comparison to capture the last subarray if it’s the maximum.

Code

Here’s the C++ code to solve this problem:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxAscendingSum(vector<int>& nums) {
        if (nums.empty()) return 0;

        int maxSum = nums[0];
        int currentSum = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i - 1]) {
                currentSum += nums[i];
            } else {
                maxSum = max(maxSum, currentSum);
                currentSum = nums[i];
            }
        }

        return max(maxSum, currentSum);
    }
};

Explanation

1. Initialization:
   • maxSum and currentSum are both initialized to the first element of the array.
2. Traversal:
   • Starting from the second element, compare with the previous element.
   • If the current element is greater, it continues the ascending subarray, so add it to currentSum.
   • If not, update maxSum with the maximum of maxSum and currentSum, then reset currentSum to the current element.
3. Final Update:
   • After the loop, make one final comparison to ensure the last computed currentSum is considered.

Time Complexity

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

This solution ensures an efficient traversal of the array, updating the sums as necessary without needing additional space beyond a few ints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?