Leetcode 1800. Maximum Ascending Subarray Sum Solution

Problem Explanation

Given an array of positive integers, we want to find the maximum sum of an ascending subarray (contiguous subsequence). An ascending subarray is a sequence of numbers where each element is strictly greater than the previous one.

We can approach this problem by creating a variable to store the current sum of the ascending subarray, another to store the maximum sum, and iterating through the array, comparing adjacent elements. As we iterate, we check if the current element is greater than the previous one, if so, we update the current sum and the maximum sum accordingly. If not, we reset the current sum to the value of the current element.

Let's walk through an example to understand the approach:

Example:

1Input: nums = [10, 20, 30, 5, 10, 50]
2Output: 65

Solution Approach

1. Initialize variables current_sum and max_sum to the first element of the array.
2. Iterate through the array (starting from index 1) and compare each element with the previous one.
3. If the current element is greater than the previous one, update the current_sum and max_sum.
4. If the current element is not greater than the previous one, reset the current_sum to the current element's value.
5. Return the max_sum once the iteration is complete.

Illustrative Example

Let's illustrate the algorithm with the example: nums = [10, 20, 30, 5, 10, 50]

1Initial values:
2current_sum = 10
3max_sum = 10
4
5Iteration 1 (nums[1] = 20):
6Since 20 > 10 (previous element):
7  - current_sum = 10 + 20 = 30
8  - max_sum = 30 (updated)
9
10Iteration 2 (nums[2] = 30):
11Since 30 > 20 (previous element):
12  - current_sum = 30 + 30 = 60
13  - max_sum = 60 (updated)
14
15Iteration 3 (nums[3] = 5):
16Since 5 is NOT > 30 (previous element):
17  - current_sum = 5 (reset)
18
19Iteration 4 (nums[4] = 10):
20Since 10 > 5 (previous element):
21  - current_sum = 5 + 10 = 15
22  - max_sum remains 60 (not updated)
23
24Iteration 5 (nums[5] = 50):
25Since 50 > 10 (previous element):
26  - current_sum = 15 + 50 = 65
27  - max_sum = 65 (updated)
28
29After completion of the iteration, max_sum = 65.
30So, the final output is 65.

Python Solution

1class Solution:
2    def maxAscendingSum(self, nums):
3        current_sum = max_sum = nums[0]
4        for i in range(1, len(nums)):
5            if nums[i] > nums[i - 1]:
6                current_sum += nums[i]
7            else:
8                current_sum = nums[i]
9            max_sum = max(max_sum, current_sum)
10        return max_sum

Java Solution

1class Solution {
2    public int maxAscendingSum(int[] nums) {
3        int currentSum = nums[0];
4        int maxSum = nums[0];
5
6        for (int i = 1; i < nums.length; i++) {
7            if (nums[i] > nums[i - 1]) {
8                currentSum += nums[i];
9            } else {
10                currentSum = nums[i];
11            }
12            maxSum = Math.max(maxSum, currentSum);
13        }
14
15        return maxSum;
16    }
17}

JavaScript Solution

1class Solution {
2    maxAscendingSum(nums) {
3        let currentSum = nums[0];
4        let maxSum = nums[0];
5
6        for (let i = 1; i < nums.length; i++) {
7            if (nums[i] > nums[i - 1]) {
8                currentSum += nums[i];
9            } else {
10                currentSum = nums[i];
11            }
12            maxSum = Math.max(maxSum, currentSum);
13        }
14
15        return maxSum;
16    }
17}

C++ Solution

1class Solution {
2public:
3    int maxAscendingSum(vector<int>& nums) {
4        int currentSum = nums[0];
5        int maxSum = nums[0];
6
7        for (int i = 1; i < nums.size(); i++) {
8            if (nums[i] > nums[i - 1]) {
9                currentSum += nums[i];
10            } else {
11                currentSum = nums[i];
12            }
13            maxSum = max(maxSum, currentSum);
14        }
15
16        return maxSum;
17    }
18};

C# Solution

1public class Solution {
2    public int MaxAscendingSum(int[] nums) {
3        int currentSum = nums[0];
4        int maxSum = nums[0];
5
6        for (int i = 1; i < nums.Length; i++) {
7            if (nums[i] > nums[i - 1]) {
8                currentSum += nums[i];
9            } else {
10                currentSum = nums[i];
11            }
12            maxSum = Math.Max(maxSum, currentSum);
13        }
14
15        return maxSum;
16    }
17}

Now we have a complete solution with explanations and code for Python, Java, JavaScript, C++, and C#.## Time Complexity

The algorithm iterates through the array once, starting from the second element. So, the time complexity of this solution is O(n), where n is the length of the input array.

Space Complexity

The solution uses constant extra space, as we only need two variables (current_sum and max_sum) to store the sums. Hence, the space complexity is O(1).

Alternatives

We can optimize the solution by using a sliding window approach. However, it would not necessarily improve the time complexity for this particular problem. To solve similar problems that require increased performance, consider using a dynamic programming approach or segment trees.

In conclusion, the solution provided is an optimal solution for finding the maximum sum of an ascending subarray using O(n) time complexity and O(1) space complexity.