Finding a specific partitioning of a finite ordered set of positive integers.

Question

Definition of partitioning

Let $S$ be a finite ordered set of positive integers. $$S = \{s_i \mid s_i \in \Bbb{Z}^+\}$$

E.g. $S = \{4, 7, 9, 8, 3, 2, 5\}$

Given this set $S$, we define $P$ as a partition of set $S$ such that:

1. $P = \{p_1, p_2, p_3, \ldots, p_k\}$.

2. $p_j$ (for some $j$) is either a singleton set or if $s_l, s_m \in p_j $ and if $l < m$, then $s_i \in p_j\ \forall i \in (l,m)$.

3. Given $p_j = \{s_i \mid l\leq i\leq m\}$, we define function $f^-$ on $p_j$ as

$$f^-(p_j) = \begin{cases} s_i, & \text{if $p_j$ is a singleton} \\ \sum_{i=l}^{m-1} |s_{i+1} - s_i|, & \text{otherwise} \end{cases}$$

Problem

Given a set $S$, find a $P$ such that,

1. $\sum f^-(p_j), \forall p_j \in P$ is minimized and,

2. $\max(|p_j|), \forall p_j \in P$ is minimized (where $|p_i|$ represents the cardinality of set $p_j$)

Example:

Let $S = \{1, 2, 8\}$, one partitioning of this set could be $P = \{\{1\}, \{2, 8\}\}$. You can verify easily that $P$ is passing the two constraints defined above.