LogoKode$word

LeetCode 3689: Maximum Total Subarray Value I – Java Greedy Solution Explained

Learn how to solve LeetCode 3689 using an efficient greedy approach in Java. Understand the intuition, dry run, complexity analysis, and why the maximum subarray value can be reused k times for the optimal solution.

Krishna Shrivastava
229 views
LinkedInGithubX
0
0
LeetCodeJavaMediumSubarray
LeetCode 3689: Maximum Total Subarray Value I – Java Greedy Solution Explained
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 3689, “Maximum Total Subarray Value I”, is an interesting medium-level array problem that focuses on maximizing the total value of selected subarrays. The challenge introduces an important observation-based greedy approach that simplifies the problem significantly.

In this article, we will break down the problem statement, understand the intuition behind the solution, analyze the Java code step-by-step, and discuss the time and space complexity.

Problem Statement

Try this problem here :- Maximum Total Subarray Value I

You are given:

  1. An integer array nums
  2. An integer k

You must choose exactly k non-empty subarrays from the array.

The value of a subarray is defined as:

Value = Maximum Element − Minimum Element

The goal is to maximize the total value of all chosen subarrays.

Example

Example 1

Input:

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

Output:

4

Explanation:

  1. Subarray [1,3] → 3 - 1 = 2
  2. Subarray [1,3,2] → 3 - 1 = 2

Total = 2 + 2 = 4

Example 2

Input:

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

Output:

12

Explanation:

The maximum possible subarray value is:

5 - 1 = 4

Choose this optimal subarray 3 times:

4 + 4 + 4 = 12

Key Observation

The problem allows:

  1. Overlapping subarrays
  2. Reusing the same exact subarray multiple times

This changes everything.

To maximize the total value:

  1. Find the maximum possible subarray value.
  2. Reuse that same subarray exactly k times.

Now the question becomes:

What is the maximum possible value of any subarray?

Since a subarray’s value is:

max(subarray) - min(subarray)

The largest possible value is simply:

global maximum element - global minimum element

So the final answer becomes:

(maxElement - minElement) * k

Java Solution

class Solution {
public long maxTotalValue(int[] nums, int k) {
long min = Long.MAX_VALUE;
long max = Long.MIN_VALUE;
long ans = 0;

for(int i = 0; i < nums.length; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}

ans = max - min;

return ans * k;
}
}

Step-by-Step Dry Run

Input

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

Step 1: Find Minimum and Maximum

Traverse the array:

ElementCurrent MinCurrent Max
444
224
525
115

Final:

min = 1
max = 5

Step 2: Calculate Maximum Subarray Value

5 - 1 = 4

Step 3: Multiply by k

4 * 3 = 12

Final Answer:

12

Why This Greedy Approach Works

The problem explicitly allows selecting:

  1. The same subarray multiple times
  2. Overlapping subarrays

So once we identify the subarray with the highest possible value, there is no reason to choose anything else.

The optimal strategy is:

Choose the best subarray repeatedly k times

This reduces the entire problem to finding:

Maximum element - Minimum element

Time Complexity

Time Complexity

O(n)

We traverse the array only once.

Space Complexity

O(1)

Only a few variables are used.

Interview Insights

This problem tests:

  1. Observation skills
  2. Greedy thinking
  3. Ability to simplify constraints
  4. Understanding of problem flexibility

Many developers initially overcomplicate the problem using sliding window or dynamic programming approaches. However, the key insight is realizing that repeated subarrays are allowed.

Final Thoughts

LeetCode 3689 is a great example of how carefully reading constraints can dramatically simplify a problem.

Instead of generating all subarrays, the optimal solution comes from a simple mathematical observation:

Maximum Total Value = (Global Max − Global Min) × k

This leads to an elegant and highly efficient O(n) solution.

If you are preparing for coding interviews, this problem is an excellent exercise in greedy optimization and pattern recognition.

Related Articles

Count Subarrays of Size K with Average ≥ Threshold — Sliding Window Solution (LeetCode 1343)

Count Subarrays of Size K with Average ≥ Threshold — Sliding Window Solution (LeetCode 1343)

Efficiently counting qualifying subarrays using an O(n) sliding window approach

Read Article
Maximum Average Subarray I — Efficient Solution Using Sliding Window (LeetCode 643)

Maximum Average Subarray I — Efficient Solution Using Sliding Window (LeetCode 643)

How to optimize subarray average calculation from brute force to an O(n) sliding window approach

Read Article
Maximum Absolute Sum of Any Subarray

Maximum Absolute Sum of Any Subarray

LeetCode Question 1749 Medium

Read Article
Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

Learn how to find the longest contiguous subarray where each element occurs at most K times using HashMap and sliding window.

Read Article
Ai Assistant Kas