Consider the following 3-PARTITION problem. Given integers a1,..., an, we want to determin...

Consider the following 3-PARTITION problem. Given integers a1,..., an, we want to determine whether it is possible to partition {1,...,n} into three disjoint subsets I, J, K such that

For example, for input (1, 2, 3, 4, 4, 5, 8) the answer is yes, because there is the partition (1, 8), (4, 5), (2, 3, 4). On the other hand, for input (2, 2, 3, 5) the answer is no.

Devise and analyze a dynamic programming algorithm for 3-PARTITION that runs in time polynomial in n and in ∑iai