- #1

- 11

- 0

## Homework Statement

Given an array of positive integers A[1, . . . , n], and an integer M > 0, you want to partition the array into segments A[1, . . . , i1], A[i_1 + 1, . . . , i2], . . . , A[i_k−1 + 1, . . . , ik], so that the sum of integers in every segment does not exceed M, while minimizing the number of segments k. You can assume that M ≥ A

*for all i (which guarantees that such a partition exists). Design an O(n) greedy algorithm for solving this problem and prove that it is optimal (i.e. that the obtained partition has the smallest possible number of segments).*

The algorithm is very easy just keep adding the values in the array until you see that the sum is greater than M, then start a new segment.

How can I prove that it's optimal?

## Homework Equations

## The Attempt at a Solution

The algorithm is very easy just keep adding the values in the array until you see that the sum is greater than M, then start a new segment.

How can I prove that it's optimal?