# Maximum Ascending Subarray Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-ascending-subarray-sum)
Canonical: https://scaleengineer.com/dsa/problems/maximum-ascending-subarray-sum
**Data structures:** Array
**Companies:** [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
Given an array of positive integers `nums`, return the **maximum** possible sum of an strictly increasing subarray in`nums`.

A subarray is defined as a contiguous sequence of numbers in an array.

**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`

# Approaches
## Brute Force with Nested Loops
This approach systematically checks every possible contiguous subarray. For each potential starting point in the array, it extends the subarray as long as the elements are strictly increasing, calculates the sum, and updates the overall maximum sum found.
**Time:** O(n^2), where `n` is the length of the input array `nums`. The two nested loops result in a quadratic runtime in the worst-case scenario (e.g., a sorted array). · **Space:** O(1), as it only uses a few variables to store sums and indices, regardless of the input size.
**Pros:** Straightforward to conceptualize and implement.; Guaranteed to be correct as it checks all possibilities.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.; Performs redundant computations by re-evaluating parts of subarrays.
### Explanation
The brute-force method iterates through all possible starting positions of a subarray. For each starting position `i`, it builds an ascending subarray by moving to the right (incrementing `j`). It keeps a `currentSum` for the subarray starting at `i` and extending to `j`. As long as `nums[j]` is greater than `nums[j-1]`, the subarray is extended, and `currentSum` is updated. If the ascending property is violated, the extension stops for the current starting point `i`. The global `maxSum` is updated whenever a `currentSum` for a valid ascending subarray is calculated. This ensures all ascending subarrays are considered, and the one with the maximum sum is found.

```java
class Solution {
    public int maxAscendingSum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int maxSum = 0;
        for (int i = 0; i < nums.length; i++) {
            int currentSum = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > nums[j - 1]) {
                    currentSum += nums[j];
                } else {
                    break;
                }
            }
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize a variable `maxSum` to 0 to store the maximum sum found.
- Iterate through the array with an outer loop using index `i` from 0 to `n-1`. This index `i` will be the starting point of a potential ascending subarray.
- For each `i`, initialize `currentSum = nums[i]`.
- Start an inner loop with index `j` from `i + 1` to `n-1`.
- Inside the inner loop, check if `nums[j] > nums[j-1]`. 
  - If it is, the subarray is still ascending. Add `nums[j]` to `currentSum`.
  - If it's not, the ascending sequence is broken. Break the inner loop.
- After the inner loop finishes (either by completion or by breaking), the `currentSum` holds the sum of the ascending subarray starting at `i`. Update `maxSum = Math.max(maxSum, currentSum)`.
- After the outer loop completes, `maxSum` will hold the result.

## Single Pass Greedy Approach
An optimal single-pass approach that iterates through the array once. It maintains the sum of the current ascending subarray. When the ascending order is broken, it compares the current sum with the maximum sum found so far and then starts a new sum. This is a greedy approach that makes the locally optimal choice at each step.
**Time:** O(n), where `n` is the length of `nums`. The algorithm involves a single loop through the array. · **Space:** O(1), as it only uses a constant number of variables (`maxSum`, `currentSum`, `i`) irrespective of the input array size.
**Pros:** Extremely efficient with a linear time complexity.; Requires constant extra space.; Simple, elegant, and the optimal solution for this problem.
**Cons:** This approach is optimal, so there are no significant cons for this problem.
### Explanation
This efficient method avoids nested loops by processing the array in a single pass. It uses a `currentSum` variable to track the sum of the ascending subarray being examined. It also uses a `maxSum` variable to keep track of the highest sum found so far. The algorithm starts by initializing both sums with the first element. Then, it iterates from the second element. If an element is greater than its predecessor, it's part of the current ascending subarray, so its value is added to `currentSum`. If it's less than or equal to its predecessor, the ascending streak is broken. At this point, the current ascending subarray ends, and a new one begins with the current element, so `currentSum` is reset to `nums[i]`. In every iteration, `maxSum` is updated to be the maximum of its current value and `currentSum`. This ensures that we always keep track of the largest sum seen.

```java
class Solution {
    public int maxAscendingSum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int maxSum = nums[0];
        int currentSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                currentSum += nums[i];
            } else {
                currentSum = nums[i];
            }
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}
```
### Algorithm
- Initialize `maxSum` and `currentSum` with the value of the first element, `nums[0]`.
- Iterate through the array from the second element (`i = 1`) to the end.
- In each iteration, compare the current element `nums[i]` with the previous one `nums[i-1]`.
- If `nums[i] > nums[i-1]`, the ascending sequence continues. Add `nums[i]` to `currentSum`.
- If `nums[i] <= nums[i-1]`, the ascending sequence is broken. Reset `currentSum` to the value of the current element `nums[i]`, as this starts a new potential ascending subarray.
- After updating `currentSum` in each step, compare it with `maxSum` and update `maxSum` if `currentSum` is larger: `maxSum = Math.max(maxSum, currentSum)`.
- After the loop finishes, return `maxSum`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxAscendingSum(vector<int> &nums) {
    int ans = 0, t = 0;
    for (int i = 0; i < nums.size(); ++i) {
      if (i == 0 || nums[i] > nums[i - 1]) {
        t += nums[i];
        ans = max(ans, t);
      } else {
        t = nums[i];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int: ans = t = 0 for i, v in enumerate(nums): if i == 0 or v > nums[i - 1]: t += v ans = max(ans, t) else: t = v return ans

```