1800 - Maximum Ascending Subarray Sum

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 [nums_l, nums_(l+1), ..., nums_(r-1), nums_r] is ascending if for all i where l <= i < r, nums_i < nums_(i+1). Note that a subarray of size 1 is ascending.

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.

Example 4:

Input: nums = [100,10,1]

Output: 100

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

Solution

Initialize the maximum sum and the sum as nums[0]. Loop over nums. For each element, if the current element is greater than the previous element, then add the current element to the sum. Otherwise, update the sum as the current element. Maintain the maximum sum and return the maximum sum. 

AVA

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

C++

// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxAscendingSum(vector<int>& A) {
        int ans = A[0], sum = A[0];
        for (int i = 1; i < A.size(); ++i) {
            if (A[i] > A[i - 1]) {
                sum += A[i];
            } else {
                sum = A[i];
            }
            ans = max(ans, sum);
        }
        return ans;
    }
};

PYTHON

class Solution:
    def maxAscendingSum(self, nums):
        ans = nums[0]
        curr_sum = nums[0]

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                curr_sum += nums[i]  # Extend the ascending subarray
            else:
                curr_sum = nums[i]  # Start a new subarray
            ans = max(ans, curr_sum)

        return ans