Skip to main content
Talentd

Maximum Total Subarray Value I - Solution & Explanation

MediumArrayGreedy5 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

You are given an integer array nums of length n and an integer k.

You need to choose exactly k non-empty subarrays nums[l..r] of nums. Subarrays may overlap, and the exact same subarray (same l and r) can be chosen more than once.

The value of a subarray nums[l..r] is defined as: max(nums[l..r]) - min(nums[l..r]).

The total value is the sum of the values of all chosen subarrays.

Return the maximum possible total value you can achieve.

 

Example 1:

Input: nums = [1,3,2], k = 2

Output: 4

Explanation:

One optimal approach is:

  • Choose nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of 3 - 1 = 2.
  • Choose nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also 3 - 1 = 2.

Adding these gives 2 + 2 = 4.

Example 2:

Input: nums = [4,2,5,1], k = 3

Output: 12

Explanation:

One optimal approach is:

  • Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of 5 - 1 = 4.
  • Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4.
  • Choose nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again 4.

Adding these gives 4 + 4 + 4 = 12.

 

Constraints:

  • 1 <= n == nums.length <= 5 * 10​​​​​​​4
  • 0 <= nums[i] <= 109
  • 1 <= k <= 105

Approach Overview

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.

Solution

We can observe that the value of a subarray only depends on the global maximum and minimum values. Therefore, we just need to find the global maximum and minimum, then multiply their difference by k.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray EnumerationO(n^2)O(1)Useful for understanding the problem by checking every subarray, but too slow for large inputs.
Greedy Positive Difference AccumulationO(n)O(1)Best approach for the general case. Single pass over the array captures all profitable increases.

Video Solution

Maximum Total Subarray Value I | Simple Observation | Leetcode 3689 | codestorywithMIK • codestorywithMIK • 5,566 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Total Subarray Value I easy or hard?
Maximum Total Subarray Value I is generally considered a Medium difficulty problem. The implementation is simple once the greedy observation is identified, but recognizing that only positive adjacent differences matter can take some practice.
Maximum Total Subarray Value I Python/Java solution
Most implementations follow the same pattern: iterate through the array and add positive differences to a result variable. The logic translates directly to Python, Java, C++, Go, or TypeScript since it relies only on basic loops and arithmetic.
How to solve Maximum Total Subarray Value I in O(n)?
Traverse the array from left to right and compute the difference between adjacent elements. Whenever nums[i] is greater than nums[i-1], add the difference to the result. This captures every profitable increase and produces the maximum total subarray value in linear time.
What is the best approach for Maximum Total Subarray Value I?
The best approach uses a greedy observation. Iterate through the array and sum every positive difference between consecutive elements. Each increase contributes to the maximum total value, giving an O(n) time and O(1) space solution.
Is Maximum Total Subarray Value I asked at Google/Amazon/Meta?
Greedy array problems with local profit accumulation patterns frequently appear in interviews at companies like Amazon, Google, and Meta. Variations are common in coding rounds because they test pattern recognition and optimal linear scanning techniques.
What data structure is used in Maximum Total Subarray Value I?
The problem primarily uses a simple array traversal with greedy logic. No additional data structures are required beyond a few variables for iteration and maintaining the running total.
What is the time complexity of Maximum Total Subarray Value I?
The optimal greedy solution runs in O(n) time because it scans the array once and performs constant work per element. Space complexity is O(1) since only a running total is stored.

Ready to solve this problem?

Practice Maximum Total Subarray Value I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays