Highest cardinality grouping of contiguous integers with minimum-sum threshold 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:


Fastest algorithm wins (computational complexity in \$O\$ notation). 
Additionally, there might be situations where an element \$l_i &gt;\!\!&gt; 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)$$
Java (JDK), 1248 bytes



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

}


Try it online!

Complexity O(n)