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
- Initialize variables
current_sum
andmax_sum
to the first element of the array. - Iterate through the array (starting from index 1) and compare each element with the previous one.
- If the current element is greater than the previous one, update the
current_sum
andmax_sum
. - If the current element is not greater than the previous one, reset the
current_sum
to the current element's value. - 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.