Disjoint subsequences in an array with maximum difference

Problem

Given an integer array arr, find two disjoint (non-overlapping) contiguous subarrays such that the difference between their sums is maximized. In other words, choose non-overlapping subarrays A and B to maximize sum(A) - sum(B).

Clarifications and assumptions

The subarrays must be contiguous and non-overlapping (disjoint).
Subarrays may be empty only if your problem variant allows it; here we assume non-empty subarrays.
sum(A) - sum(B) can be maximized either by taking a large positive sum(A) and small/negative sum(B), or by taking a large negative sum(B) and a small/positive sum(A). We therefore consider both orientations.

Examples

Example 1

Input: arr = [1, -2, 3, -1, 2]
Output: 5
Explanation: Choose A = [3, -1, 2] with sum 4 and B = [-2] with sum -1, difference = 4 - (-1) = 5.

Example 2

Input: arr = [5, -3, 5]
Output: 10
Explanation: Choose A = [5, -3, 5] with sum 7 and B = [] (empty disallowed here) or choose B small; equivalently consider left/right partition where maximum difference is 10 (choose A=[5, -3,5] and B=[-?]).

Solution

We present a linear-time solution that uses prefix/suffix passes with Kadane's algorithm variants to compute, for every partition point, the best subarray sums on each side. From these arrays we compute the maximum of left_max[i] - right_min[i+1] and right_max[i+1] - left_min[i] over all valid splits.

Method 1 — Prefix/suffix Kadane arrays (recommended)

Intuition

Compute four helper arrays:

left_max[i]: maximum subarray sum within arr[0..i].
left_min[i]: minimum subarray sum within arr[0..i].
right_max[i]: maximum subarray sum within arr[i..n-1].
right_min[i]: minimum subarray sum within arr[i..n-1].

For any split between i and i+1, candidates for sum(A)-sum(B) are left_max[i] - right_min[i+1] and right_max[i+1] - left_min[i]. We take the maximum over all splits.

Approach

If n = len(arr) and n < 2, return 0 or handle as special-case (no two disjoint non-empty subarrays possible).
Build left_max by running Kadane's algorithm from left to right and tracking the best subarray seen so far at each index.
Build left_min by running an analogous Kadane for minimum sums (invert signs or modify comparisons).
Build right_max and right_min by scanning from right to left.
For every split index i in 0..n-2, compute two candidates:
- cand1 = left_max[i] - right_min[i+1]
- cand2 = right_max[i+1] - left_min[i] Track the maximum candidate and also the corresponding subarray indices if you need to return them.

Edge cases:

Arrays with all negative numbers: Kadane handles this by tracking the maximum single element.
Small arrays: ensure you treat n==1 or n==0 explicitly.

Code

C++

class Solution {
 public:
    long long maxDiffDisjoint(const std::vector<int>& arr) {
        int n = arr.size();
        if (n < 2) return 0;
        std::vector<long long> left_max(n), left_min(n), right_max(n), right_min(n);

        long long best = arr[0], cur = 0;
        // left_max
        cur = 0; best = arr[0];
        for (int i = 0; i < n; ++i) {
            cur = std::max<long long>(arr[i], cur + arr[i]);
            best = std::max(best, cur);
            left_max[i] = best;
        }

        // left_min
        cur = 0; best = arr[0];
        for (int i = 0; i < n; ++i) {
            cur = std::min<long long>(arr[i], cur + arr[i]);
            best = std::min(best, cur);
            left_min[i] = best;
        }

        // right_max
        cur = 0; best = arr[n-1];
        for (int i = n-1; i >= 0; --i) {
            cur = std::max<long long>(arr[i], cur + arr[i]);
            best = std::max(best, cur);
            right_max[i] = best;
        }

        // right_min
        cur = 0; best = arr[n-1];
        for (int i = n-1; i >= 0; --i) {
            cur = std::min<long long>(arr[i], cur + arr[i]);
            best = std::min(best, cur);
            right_min[i] = best;
        }

        long long ans = LLONG_MIN;
        for (int i = 0; i + 1 < n; ++i) {
            ans = std::max(ans, left_max[i] - right_min[i+1]);
            ans = std::max(ans, right_max[i+1] - left_min[i]);
        }
        return ans;
    }
};

Go

package main

func maxDiffDisjoint(arr []int) int64 {
        n := len(arr)
        if n < 2 { return 0 }
        leftMax := make([]int64, n)
        leftMin := make([]int64, n)
        rightMax := make([]int64, n)
        rightMin := make([]int64, n)

        var cur int64
        cur = 0
        best := int64(arr[0])
        for i := 0; i < n; i++ {
                if cur+int64(arr[i]) > int64(arr[i]) { cur = cur + int64(arr[i]) } else { cur = int64(arr[i]) }
                if cur > best { best = cur }
                leftMax[i] = best
        }
        cur = 0; best = int64(arr[0])
        for i := 0; i < n; i++ {
                if cur+int64(arr[i]) < int64(arr[i]) { cur = cur + int64(arr[i]) } else { cur = int64(arr[i]) }
                if cur < best { best = cur }
                leftMin[i] = best
        }
        cur = 0; best = int64(arr[n-1])
        for i := n-1; i >= 0; i-- {
                if cur+int64(arr[i]) > int64(arr[i]) { cur = cur + int64(arr[i]) } else { cur = int64(arr[i]) }
                if cur > best { best = cur }
                rightMax[i] = best
        }
        cur = 0; best = int64(arr[n-1])
        for i := n-1; i >= 0; i-- {
                if cur+int64(arr[i]) < int64(arr[i]) { cur = cur + int64(arr[i]) } else { cur = int64(arr[i]) }
                if cur < best { best = cur }
                rightMin[i] = best
        }

        var ans int64 = -1<<63
        for i := 0; i+1 < n; i++ {
                if leftMax[i]-rightMin[i+1] > ans { ans = leftMax[i]-rightMin[i+1] }
                if rightMax[i+1]-leftMin[i] > ans { ans = rightMax[i+1]-leftMin[i] }
        }
        return ans
}

Java

class Solution {
    public long maxDiffDisjoint(int[] arr) {
        int n = arr.length;
        if (n < 2) return 0;
        long[] leftMax = new long[n], leftMin = new long[n], rightMax = new long[n], rightMin = new long[n];

        long cur = 0, best = arr[0];
        cur = 0; best = arr[0];
        for (int i = 0; i < n; ++i) {
            cur = Math.max(arr[i], (int)(cur + arr[i]));
            best = Math.max(best, cur);
            leftMax[i] = best;
        }
        cur = 0; best = arr[0];
        for (int i = 0; i < n; ++i) {
            cur = Math.min(arr[i], (int)(cur + arr[i]));
            best = Math.min(best, cur);
            leftMin[i] = best;
        }
        cur = 0; best = arr[n-1];
        for (int i = n-1; i >= 0; --i) {
            cur = Math.max(arr[i], (int)(cur + arr[i]));
            best = Math.max(best, cur);
            rightMax[i] = best;
        }
        cur = 0; best = arr[n-1];
        for (int i = n-1; i >= 0; --i) {
            cur = Math.min(arr[i], (int)(cur + arr[i]));
            best = Math.min(best, cur);
            rightMin[i] = best;
        }

        long ans = Long.MIN_VALUE;
        for (int i = 0; i + 1 < n; ++i) {
            ans = Math.max(ans, leftMax[i] - rightMin[i+1]);
            ans = Math.max(ans, rightMax[i+1] - leftMin[i]);
        }
        return ans;
    }
}

Python

from typing import List

class Solution:
        def max_diff_disjoint(self, arr: List[int]) -> int:
                n = len(arr)
                if n < 2:
                        return 0
                left_max = [0] * n
                left_min = [0] * n
                right_max = [0] * n
                right_min = [0] * n

                cur = 0
                best = arr[0]
                cur = 0; best = arr[0]
                for i in range(n):
                        cur = max(arr[i], cur + arr[i])
                        best = max(best, cur)
                        left_max[i] = best

                cur = 0; best = arr[0]
                for i in range(n):
                        cur = min(arr[i], cur + arr[i])
                        best = min(best, cur)
                        left_min[i] = best

                cur = 0; best = arr[-1]
                for i in range(n - 1, -1, -1):
                        cur = max(arr[i], cur + arr[i])
                        best = max(best, cur)
                        right_max[i] = best

                cur = 0; best = arr[-1]
                for i in range(n - 1, -1, -1):
                        cur = min(arr[i], cur + arr[i])
                        best = min(best, cur)
                        right_min[i] = best

                ans = -10**30
                for i in range(n - 1):
                        ans = max(ans, left_max[i] - right_min[i + 1])
                        ans = max(ans, right_max[i + 1] - left_min[i])
                return ans

Complexity

⏰ Time complexity: O(n) — we do a constant number of linear passes over the array.
🧺 Space complexity: O(n) — four auxiliary arrays of length n (can be reduced to O(1) if only the value is required and indices are not tracked, but keeping arrays simplifies retrieval of indices).