Problem
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 [numsl, numsl+1, ..., numsr-1, numsr]
is ascending if for all i
where l <= i < r
, numsi < numsi+1
. Note that a subarray of size 1
is ascending.
Examples
Example 1:
Input: nums = [10,20,30,5,10,50]
Output: 65
Explanation:[5,10,50] is the ascending subarray with the maximum sum of 65.
Example 2:
Input: nums = [10,20,30,40,50]
Output: 150
Explanation:[10,20,30,40,50] is the ascending subarray with the maximum sum of 150.
Example 3:
Input: nums = [12,17,15,13,10,11,12]
Output: 33
Explanation:[10,11,12] is the ascending subarray with the maximum sum of 33.
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 100
Solution
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Naive
The naive approach to solving this problem involves checking all possible subarrays to identify those that are ascending and calculating their sums. Here’s how the naive approach works:
- We initialize
maxSum
to the smallest possible integer value. - Loop through each index
i
from0
ton-1
as the starting point of the subarray. - For each starting point, initialize
currSum
to0
and extend the subarray to the right (fromi
ton-1
). Add each element tocurrSum
. - If the next element is not greater than the current one, break the inner loop.
- Track the maximum sum encountered during the process.
Code
Java
class Solution {
public int maxAscendingSum(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int n = nums.length;
for (int i = 0; i < n; i++) {
int currSum = 0;
for (int j = i; j < n; j++) {
currSum += nums[j];
maxSum = Math.max(maxSum, currSum);
if (j < n - 1 && nums[j] >= nums[j+1]) {
break;
}
}
}
return maxSum;
}
}
Python
class Solution:
def maxAscendingSum(self, nums: List[int]) -> int:
max_sum = float('-inf')
n = len(nums)
for i in range(n):
curr_sum = 0
for j in range(i, n):
curr_sum += nums[j]
max_sum = max(max_sum, curr_sum)
if j < n - 1 and nums[j] >= nums[j + 1]:
break
return max_sum
Complexity
- ⏰ Time complexity:
O(n^2)
, because of nested loop. - 🧺 Space complexity:
O(1)
, because we are only using a fixed amount of extra space for the variablemax_sum
.
Method 2 - Kadane like logic
The problem requires finding the maximum possible sum of an ascending subarray. To achieve this, we can iterate through the array while maintaining the sum of the current ascending subarray and updating the maximum sum whenever a higher sum is found. If a number breaks the ascending property, we reset the current sum to start a new potential ascending subarray.
Approach
- Initialize
ans
to store the maximum sum found so far, andcurrent_sum
to maintain the sum of the current ascending subarray. - Iterate through the array. For each element:
- If it is the start of the array or maintains the ascending property with respect to the previous element, add it to
current_sum
. - Otherwise, update
ans
ifcurrent_sum
is greater thanans
, and resetcurrent_sum
to the current element.
- If it is the start of the array or maintains the ascending property with respect to the previous element, add it to
- After the loop, make sure to update
ans
withcurrent_sum
one last time in case the longest ascending subarray is at the end of the array. - Return
ans
, which holds the maximum sum of an ascending subarray.
Code
Java
class Solution {
public int maxAscendingSum(int[] nums) {
int ans = nums[0], currSum = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] < nums[i]) {
currSum += nums[i];
} else {
currSum = nums[i];
}
ans = Math.max(ans, currSum);
}
return ans;
}
}
Python
class Solution:
def maxAscendingSum(self, nums: List[int]) -> int:
ans = nums[0]
curr_sum = nums[0]
for i in range(1, len(nums)):
if nums[i - 1] < nums[i]:
curr_sum += nums[i]
else:
curr_sum = nums[i]
ans = max(ans, curr_sum)
return ans
Complexity
- ⏰ Time complexity:
O(n)
, because we iterate through the array exactly once. - 🧺 Space complexity:
O(1)
, because we use only a fixed amount of extra space regardless of the input size.