Highest cardinality grouping of contiguous integers with minimum-sum threshold

Question

Challenge

Given an array of positive integers and a threshold, the algorithm should output a set of consecutive-element-groupings (subarrays) such that each group/subarray has a sum greater than the threshold.

Rules

The solution should honor two additional criteria:

• be of highest cardinality of the groups (i.e. highest number of groups)
• having the maximum group-sum be as lowest as possible.

Mathematical Description:

• input array \$L = [l_1, l_2, ..., l_n]\$
• threshold \$T\$

output groups/subarrays \$G = [g_1, g_2, ..., g_m]\$ where:

• \$m \leq n\$
• \$\bigcap\limits_{i=1}^m{g_i}=\varnothing\$
• \$\bigcup\limits_{i=1}^m{g_i}=L\$
• if we denote the sum of elements in a group as \$s_{g_i} = \sum\limits_{l \in g_i}l\$, then all groups have sum greater than threshold \$T\$. In other words: \$\underset{g \in G}{\operatorname{min}}{\{s_g\}} \ge T\$
• if cardinality \$|g_i|=k\$, then \$g_i=[l_j, ..., l_{j+k-1}]\$ for an arbitrary \$j\$ (i.e. all elements are consecutive).
• optimal solution has highest cardinality: \$|G_{opt}| \ge \max\left(|G| \right),,円,円\forall G\$
• optimal solution \$G_{opt}\$ has lowest maximum group-sum: \$\underset{g \in G_{opt}}{\operatorname{max}}{\{s_g\}} \le \underset{g \in G}{\operatorname{max}}{\{s_g\}}, ,円,円,円 \forall G\$

Assumption

for simplicity, we assume such a solution exists by having: \$\sum\limits_{i=1}^n l_i \ge T\$

Example:

Example input:

L = [1, 4, 12, 6, 20, 10, 11, 3, 13, 12, 4, 4, 5] 
T = 12

Example output:

G = {
 '1': [1, 4, 12, 6],
 '2': [20], 
 '3': [10, 11], 
 '4': [3, 13], 
 '5': [12], 
 '6': [4, 4, 5]
}

Winning Criteria:

1. Fastest algorithm wins (computational complexity in \$O\$ notation).
2. Additionally, there might be situations where an element \$l_i >\!\!> T\$ is really big, and thus it becomes its own group; causing the maximum subarray sum to be always a constant \$l_i\$ for many potential solutions \$G\$.
   Therefore, if two potential solutions \$G_A\$ and \$G_B\$ exists, the winning algorithm is the one which results in output that has the smallest max-subarray-sum amongst the non-intersecting groups.
   In other words: if we denote \$G_{A \cap B}=\{g_i: ,円,円 g_i \in G_A \cap G_B\}\$, then optimum grouping, \$G_{opt}\$, is the one that has:

$$\underset{g \in \mathbf{G_{opt}} - G_{A \cap B}}{\operatorname{max}}{\{s_g\}} = \min\left( \underset{g \in \mathbf{G_A} - G_{A \cap B}}{\operatorname{max}}{\{s_g\}},円 , ,円,円\underset{g \in \mathbf{G_{B}} - G_{A \cap B}}{\operatorname{max}}{\{s_g\}} \right)$$

• Mike Ponemariko: Thanks @Arnauld for letting me know the rules, I make the change now.
• Jonathan Allan: Shouldn't the example result be [[1, 4, 12, 6], [20], [10, 11], [3, 13], [12], [4, 4, 5]] ? This has six entries too, but the maximal sum is lower at 23 (rather than 26).
• Mike Ponemariko: @JonathanAllan, corrected it. Thanks for pointing it out.
• Mike Ponemariko: made the change @Arnauld

Answer 1

Java (JDK), 1248 bytes

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class TestCG{
	public static void main(String [] args) {
		int [] input = new int[] {1,4,12,6,20,10,11,3,13,12,4,4,5};
		int threshold = 12;
		List<List<Integer>> groups = new ArrayList<>();
		
		int currentGroupSum = 0;
		int previousGroupSum = 0;
		
		int maxGroupSum = 0;
		int boundaryValue = 0;
		List<Integer> currentGroup = new ArrayList<>();
		
		for(int i=0; i<input.length; i++) {
			currentGroup.add(input[i]);
			currentGroupSum+=input[i];
			
			if(currentGroupSum>=threshold) {
				if(i<input.length-1) {
					boundaryValue = input[i+1];
				}
				
				if(currentGroupSum>maxGroupSum) {
					maxGroupSum = currentGroupSum;
				}
				
 if(currentGroupSum > previousGroupSum && (currentGroupSum - boundaryValue)>=threshold) {
  
 	groups.get(groups.size()-1).add(boundaryValue);
 	currentGroup.remove(0);
 }
				
				previousGroupSum = currentGroupSum;
				
				
				currentGroupSum = 0;
				groups.add(currentGroup);
				currentGroup = new ArrayList<>();
			}
		}
		System.out.println(groups.size());	
		
		for(List<Integer> group : groups) {
			System.out.println(group);
		}
	}
}

Try it online!

Complexity O(n)

• Unrelated String: Welcome to CG&CC! This doesn't seem to specify the language it's written in (I'm assuming Java, or some relative thereof?) or its complexity (which is relevant because the winning criterion for this challenge is lowest complexity). You should probably edit your answer to state both of those things, and while you're at it also provide a link to an online interpreter for your code, such as Try It Online!.
• Pranav83: Apologies as it was my first submission, have included online link.

Answer 2

Prolog: \$ O(n^2) \$, 785 bytes

:- use_module(library(clpz)).
:- use_module(library(lists)).
sum(Ls, S) :-
 sum_(Ls, 0, S).
sum_([], S, S).
sum_([L|Ls], S0, S) :-
 S1 #= L + S0,
 sum_(Ls, S1, S).
solve([], _, _, []).
solve(Ls, T, M, Ms) :-
 T > 0,
 solve_(Ls, T, M, [], Ms1),
 reverse(Ms1, Ms).
solve_([], _, _, Ms, Ms).
solve_(Ls, T, M, Ms0, Ms) :-
 append(As, Bs, Ls),
 As = [_|_],
 sum(As, S),
 S #>= T,
 S #=< M,
 solve_(Bs, T, M, [As|Ms0], Ms).
solution(Ls, T, Ms, M) :-
 solution_(Ls, T, Ms, sup, M).
solution_(Ls, T, Ms, M0, M) :-
 M1 in 0..M0,
 solve(Ls, T, M1, _),
 !,
 clpz:fd_get(M1, from_to(n(M2), _), _),
 M3 #= M2 - 1,
 ( solution_(Ls, T, Ms, M3, M), !
 ; end_(Ls, T, Ms, M2, M)
 ).
end_(Ls, T, Ms, M, M) :- solve(Ls, T, M, Ms).

To run it:

?- solution([1, 4, 12, 6, 20, 10, 11, 3, 13, 12, 4, 4, 5], 12, Ms, M).
 Ms = [[1,4,12,6],[20],[10,11],[3,13],[12],[4,4,5]], M = 23.
?- 

• Wheat Wizard: What is the complexity of the algorithm? It is necessary for scoring.
• Quantic_Solver: Yes, it is but I can't compute it yet.