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)$$

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)

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.
?-