Implement text formatter and sum subarray products

1. Text formatter (LC-inspired variant): Given an array of words and an integer maxWidth W >= 1, break the words into lines so that the total length of words on each line plus spaces is at most W. For every line except the last, place exactly one space between adjacent words, then append all remaining padding spaces after the final word so the line length is exactly W. The last line should be left-justified with single spaces between words and any remaining spaces appended at the end to reach W. Do not split words. Return the list of lines as strings and explain your algorithm and its time/space complexity.

2. Sum of subarray products: Given an integer array items[0..n-1], compute S = ∑{i=0}^{n-1} ∑{j=i}^{n-1} (∏_{k=i}^{j} items[k]). Return S.

Left-Justified Text Formatter

Given an array of words and an integer maxWidth W (W >= 1), break the words into lines so that the total length of the words on each line, plus the single spaces between adjacent words, is at most W. Place exactly one space between adjacent words on every line, then append all remaining padding spaces after the final word so the line length is exactly W (this applies to every line, including the last). A word is never split across lines, and you greedily pack as many words as fit onto each line before moving on. Return the list of formatted lines.

Example: words = ["This", "is", "an", "example", "of", "text", "justification."], W = 16 returns ["This is an ", "example of text ", "justification. "].

Constraints

• 1 <= maxWidth <= 1000
• 0 <= number of words <= 10^4
• 1 <= len(word) <= maxWidth for every word (no word is longer than the line width)
• Words contain non-space printable characters

Hints

1. Greedily pack words: keep adding the next word to the current line while the running length plus one space plus the next word still fits within maxWidth.
2. Join the chosen words with single spaces, then append (maxWidth - currentLength) trailing spaces so every line is exactly maxWidth characters.
3. Because every line (including the last) is left-justified with the same padding rule, you do not need a special case for the final line.

Sum of All Subarray Products

Given an integer array items[0..n-1], compute the sum over every contiguous subarray of the product of that subarray's elements:

S = sum over i from 0..n-1 of ( sum over j from i..n-1 of ( product of items[k] for k from i..j ) )

Return S. The array may contain zeros and negative numbers, and an empty array sums to 0.

Example: items = [1, 2, 3]. The six subarrays are [1]=1, [2]=2, [3]=3, [1,2]=2, [2,3]=6, [1,2,3]=6, so S = 1+2+3+2+6+6 = 20.

Constraints

• 0 <= n <= 10^5
• items[k] may be negative, zero, or positive
• The final sum fits in a 64-bit signed integer for the given limits (use long / long long in Java / C++)

Hints

1. Let suffix(i) be the sum of products of all subarrays that START at index i. Then suffix(i) = items[i] * (1 + suffix(i+1)): items[i] alone contributes items[i]*1, and extending each subarray starting at i+1 by items[i] contributes items[i]*suffix(i+1).
2. Process the array from right to left, maintaining a single 'running' value equal to suffix(i), and add it to the total at each step. This gives an O(n) one-pass solution.
3. Be careful with zeros (a subarray containing a zero contributes 0) and negatives (products can flip sign) — the recurrence handles both automatically; no special-casing is needed.