Constant Subsequence
Source: codechef
Difficulty: 2008

Constant Subsequence
Alice has an array$A$of length$N$, and her goal is to rearrange the array in a way that minimises the maximum subarray sum of the resulting array.
However, Alice must keep the relative order of all non-negative and negative elements the same as in the original array. In other words:
The non-negative numbers should appear in the same order as they originally appeared in$A$.
The negative numbers should appear in the same order as they originally appeared in$A$.
You are tasked with finding the minimum possible value of the maximum subarray sum after rearranging the array according to these rules.
Note:
The sum of an empty subarray is$0$.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains a integer$N$— the length of the array.
The second line of each test case contains$N$space-separated integers - values of the array$A$.
Output Format
For each test case, output on a new line the minimum possible value of the maximum subarray sum after rearranging the array according to these rules.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 2\cdot 10^5$$-10^9 \leq A_i  \leq 10^9$The sum of$N$over all test cases won't exceed$2\cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:
There can be many other ways; one such rearrangement is:$[1, 2, -1, -2] \xrightarrow{} [1, -1, -2, 2]$and final maximum subarray sum will be$2$. It can be proven that this is the least possible following the rules.
Test case$2$:
Since all the elements are negative, we can choose an empty subarray, which results in a maximum subarray sum of$0$.
Test case$3$:
There can be many other ways; one such rearrangement is:$[-2, 3, 0, 2] \xrightarrow{} [3, 0, -2, 2]$and final maximum subarray sum will be$3$. It can be proven that this is the least possible following the rules.

Sample Input:
3
4
1 2 -1 -2
2
-1 -1
4
-2 3 0 2

Sample Output:
2
0
3

C++ solution:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define MOD 1000000007 
#define all(v) v.begin(),v.end()
#define print(v) for(int i = 0; i<v.size(); i++)cout<< v[i] <<" \n"[i==v.size()-1];
#define input(v) for(int i = 0; i<v.size(); i++)cin >> v[i];
const int M = 998244353;
bool check ( int mid , vector < int > &pos , vector < int > & neg){
     int s = 0 , mx = 0 , j = 0;
     for ( int i = 0; i < pos.size(); i ++ ){
           s += pos[i];
           while ( j < neg.size() && s > mid ){
                s = max ( pos[i] , s + neg[j] );
                j ++ ;
           }
           if ( s > mid ) return false;
     }
     return true;
}
void solve( int tc ){
       int n;
       cin >> n;
       vector < int > pos , neg;
       for ( int i = 0; i < n; i ++ ){
             int x;
             cin >> x;
             if ( x > 0) pos.push_back(x);
             else neg.push_back(x);
       }
       if ( pos.empty() ){
               cout << 0 << endl;
               return;
       }
       int lo = *max_element(all(pos));
       int hi = accumulate(all(pos) , 0ll);
       int ans = 0;
       while ( lo <= hi ){
            int mid = hi + lo ;
            mid /= 2;
            if ( check(mid , pos , neg )){
                ans = mid ;
                hi = mid - 1;
            }
            else lo = mid + 1;
       }
       cout << ans << endl;
}


int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) {
        solve(i);
    }

    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func check(pos, neg []int, mid int) bool {
	currSum := pos[0]
	i := 1
	j := 0

	for i < len(pos) {
		if currSum > mid {
			return false
		}
		if currSum+pos[i] > mid {
			if j >= len(neg) {
				return false
			}
			currSum += neg[j]
			j++
			if currSum < 0 {
				currSum = 0
			}
		} else {
			currSum += pos[i]
			i++
		}
	}
	return currSum <= mid
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var T int
	scanner.Scan()
	T, _ = strconv.Atoi(scanner.Text())

	for t := 0; t < T; t++ {
		var N int
		scanner.Scan()
		N, _ = strconv.Atoi(scanner.Text())

		nums := make([]int, N)
		for i := 0; i < N; i++ {
			scanner.Scan()
			num, _ := strconv.Atoi(scanner.Text())
			nums[i] = num
		}

		pos := make([]int, 0)
		neg := make([]int, 0)
		for _, num := range nums {
			if num > 0 {
				pos = append(pos, num)
			} else if num < 0 {
				neg = append(neg, num)
			}
		}

		if len(pos) == 0 {
			fmt.Fprintln(writer, 0)
			continue
		}

		if len(neg) == 0 {
			sum := 0
			for _, num := range pos {
				sum += num
			}
			fmt.Fprintln(writer, sum)
			continue
		}

		low := maxIntSlice(pos)
		high := sumIntSlice(pos)
		ans := high

		for low <= high {
			mid := low + (high-low)/2
			if check(pos, neg, mid) {
				ans = mid
				high = mid - 1
			} else {
				low = mid + 1
			}
		}

		fmt.Fprintln(writer, ans)
	}
}

func maxIntSlice(slice []int) int {
	max := slice[0]
	for _, v := range slice {
		if v > max {
			max = v
		}
	}
	return max
}

func sumIntSlice(slice []int) int {
	sum := 0
	for _, v := range slice {
		sum += v
	}
	return sum
}

Java solution:
import java.io.*;
import java.util.*;

class Codechef {
    private static boolean valid(long limit, List<Long> pos, List<Long> neg){
        int i =0, j = 0;
        long sum = 0;
        while(i < pos.size() || j < neg.size()){
            if(i < pos.size() && sum + pos.get(i) <= limit){
                sum += pos.get(i);
                i++;
            }else if(j < neg.size()){
                sum += neg.get(j);
                j++;
                if(sum < 0) sum = 0;
            }else return false;
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());

        while (t-- > 0) {
            String nk[] = br.readLine().split(" ");
            int n = Integer.parseInt(nk[0]);
            // int k = Integer.parseInt(nk[1]);

            int[] arr = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine()); // Using StringTokenizer for array input

            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            
            List<Long> pos = new ArrayList<>();
            List<Long> neg = new ArrayList<>();
            long high = 0;
            for(int ele : arr){
                if(ele >= 0) {
                    pos.add((long)ele);
                    high += ele;
                }
                else neg.add((long)ele);
            }
            
            long low = 0;
            long ans = 0;   
            while(low <= high){
                long mid = (low + high)/2;
                if(valid(mid, pos, neg)){
                    ans = mid;
                    high = mid -1;
                }else{
                    low = mid + 1;
                }
            }
            System.out.println(ans);
        }
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _ | '_/ _ / _ \ V  V / _ || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github :  https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

// Template Starts here Fast IO!

const V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];


if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

// Read input
const readline = require('readline');
const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
});

let input = [];
let currentLine = 0;

rl.on('line', (line) => {
        input.push(line);
});

rl.on('close', () => {
        main();
});

function readLine() {
        return input[currentLine++];
}

function canAchieve(M, pos, neg) {
        let i = 0,
                j = 0;
        const nPos = pos.length,
                nNeg = neg.length;
        let state = 0n;
        
        while (i < nPos || j < nNeg) {
                if (i < nPos && state + pos[i] <= M) {
                        state += pos[i];
                        i++;
                } else if (j < nNeg) {
                        state += neg[j];
                        j++;
                        if (state < 0n) state = 0n;
                } else {
                        return false;
                }
        }
        return true;
}

function main() {
        const T = parseInt(readLine());
        
        for (let t = 0; t < T; t++) {
                const N = parseInt(readLine());
                const arr = readLine().split(' ').map(BigInt);
                
                const pos = [],
                        neg = [];
                for (let i = 0; i < N; i++) {
                        if (arr[i] >= 0n) {
                                pos.push(arr[i]);
                        } else {
                                neg.push(arr[i]);
                        }
                }
                
                if (pos.length === 0) {
                        console.log(0);
                        continue;
                }
                
                let lo = 0n;
                for (const p of pos) {
                        lo = lo > p ? lo : p;
                }
                
                let hi = 0n;
                for (const p of pos) {
                        hi += p;
                }
                
                let ans = hi;
                while (lo <= hi) {
                        const mid = lo + (hi - lo) / 2n;
                        if (canAchieve(mid, pos, neg)) {
                                ans = mid;
                                hi = mid - 1n;
                        } else {
                                lo = mid + 1n;
                        }
                }
                
                console.log(ans.toString());
        }
}

Python solution:
import pathlib
import sys
from collections.abc import Iterator
from io import StringIO
from typing import final


@final
class InputReader:
    def __init__(self, source: str) -> None:
        self.source = StringIO(source)

    def read_int(self) -> int:
        return int(self.source.readline())

    def read_ints_generator(self) -> Iterator[int]:
        return map(int, self.source.readline().split())

    def read_ints(self, n: int) -> list[int]:
        values = list(self.read_ints_generator())
        assert len(values) == n
        return values

    def read_binary_as_bits(self, n: int) -> list[int]:
        values = list(map(int, self.source.readline()))
        assert len(values) == n
        return values

    def read_str(self) -> str:
        return self.source.readline().strip()


def main() -> None:
    if not sys.stdin.isatty():
        data = sys.stdin.read()
        input_reader = InputReader(data)
        for line in solve(input_reader):
            print(line)
    else:
        fp = pathlib.Path(__file__).parent / pathlib.Path("../tests/p5169/input.txt")
        if fp.is_file():
            data = fp.read_text()
        else:
            import copykitten

            data = copykitten.paste().replace("\r\n", "\n")
            fp.parent.mkdir(parents=True, exist_ok=True)
            _ = fp.write_text(data)

        input_reader = InputReader(data)
        with (fp.parent / "output.txt").open("w") as f:
            for line in solve(input_reader):
                _ = f.write(line + "\n")
                print(line)


def solve(ir: InputReader) -> Iterator[str]:
    """Solver for `https://www.codechef.com/problems/P5169`."""
    t = ir.read_int()
    for _ in range(t):
        n = ir.read_int()
        a = ir.read_ints(n)

        positives = [x for x in a if x > 0]
        negatives = [x for x in a if x < 0]
        # zeros do not change the answer so we can ignore them
        # the minimal possible subarray sum is either 0, the maximum element or the sum of all elements
        min_subarray_sum = max(0, *a, sum(a))
        max_subarray_sum = sum(positives)

        while min_subarray_sum < max_subarray_sum:
            target = (min_subarray_sum + max_subarray_sum) // 2
            pos_i = 0
            neg_i = 0
            worst_sum = 0
            current_sum = 0
            while pos_i < len(positives):
                if current_sum + positives[pos_i] <= target:
                    current_sum += positives[pos_i]
                    worst_sum = max(worst_sum, current_sum)
                    pos_i += 1
                elif neg_i < len(negatives):
                    current_sum = max(0, current_sum + negatives[neg_i])
                    neg_i += 1
                else:
                    current_sum += sum(positives[pos_i:])
                    worst_sum = max(worst_sum, current_sum)
                    break

            if worst_sum <= target:
                max_subarray_sum = worst_sum
            else:
                min_subarray_sum = target + 1

        yield str(max_subarray_sum)


if __name__ == "__main__":
    main()

Ruby solution:
def solve
  input = $stdin.each_line.to_a
  idx = 0
  t = input[idx].to_i
  idx += 1
  t.times do
    n = input[idx].to_i
    idx += 1
    a = input[idx].split.map(&:to_i)
    idx += 1
    
    positives = a.select { |x| x > 0 }
    negatives = a.select { |x| x < 0 }
    
    min_subarray_sum = [0, *a, a.sum].max
    max_subarray_sum = positives.sum
    
    while min_subarray_sum < max_subarray_sum
      target = (min_subarray_sum + max_subarray_sum) / 2
      pos_i = 0
      neg_i = 0
      worst_sum = 0
      current_sum = 0
      
      while pos_i < positives.size
        if current_sum + positives[pos_i] <= target
          current_sum += positives[pos_i]
          worst_sum = [worst_sum, current_sum].max
          pos_i += 1
        elsif neg_i < negatives.size
          current_sum = [0, current_sum + negatives[neg_i]].max
          neg_i += 1
        else
          current_sum += positives[pos_i..-1].sum
          worst_sum = [worst_sum, current_sum].max
          break
        end
      end
      
      if worst_sum <= target
        max_subarray_sum = worst_sum
      else
        min_subarray_sum = target + 1
      end
    end
    
    puts max_subarray_sum
  end
end

solve