Maximum Total Subarray Value I - Solution & Explanation

Problem Overview: You are given an integer array and need to split it into one or more subarrays so the total "value" across chosen subarrays is maximized. The key observation is that extending a subarray is only beneficial when the next element increases the value contribution. This leads to a greedy scan across the array.

Approach 1: Simple Observation (Greedy) (Time: O(n), Space: O(1))

The optimal strategy comes from noticing that only positive increases between consecutive elements add useful value. When nums[i] > nums[i-1], extending the current segment increases the subarray’s contribution. When the sequence drops or stays flat, continuing the segment provides no additional gain, so it is safe to effectively start a new subarray.

Implementation is straightforward: iterate once through the array and accumulate every positive difference nums[i] - nums[i-1]. Each positive jump represents value that can be captured by forming or extending a profitable subarray. Negative or zero differences are ignored because they do not increase the total value.

This greedy reasoning works because the contribution of each increasing step is independent. Whether you treat the increase as part of one long subarray or several smaller ones, the total accumulated gain remains the same. Summing all positive differences therefore gives the maximum possible total value.

The algorithm performs a single pass over the array and maintains only a running total, resulting in O(n) time and O(1) extra space. The technique relies on identifying local profitable transitions, a common pattern in greedy algorithms and sequential processing of arrays.

Recommended for interviews: Interviewers expect the greedy observation. A brute force approach that enumerates all possible subarrays quickly becomes quadratic and unnecessary. Recognizing that only positive adjacent differences contribute demonstrates strong problem‑solving intuition and familiarity with greedy patterns.