Problem Statement
An array A is called positive partitionable if we can divide A into one or more contiguous subarrays such that each element belongs to exactly one of the subarrays and the sum of each subarray is positive.
For example, the array {3,-7,8} is positive partitionable. One valid way of splitting this array is to split it into {3} and {-7,8}. The array {0,1,0,1,2} is also positive partitionable. The array {-1,2,-3,4,-5} and the array {0} are not positively partitionable.
A partition of an array can be described by listing the lengths of the partitions, in order. For example, {3} has length 1 and {-7,8} has length 2, hence the partition of {3,-7,8} into {3} and {-7,8} can be described by the sequence {1,2}. The sequences {2,3}, {2,2,1}, and {4,1} describe different three valid ways of partitioning the sequence {0,1,0,1,2}.
You are given the int[] a. If this array is positive partitionable, find any valid way to partition it and return a int[] that describes it (as defined in the previous paragraph). If this array isn't positive partitionable, return {-1} instead.
Definition
- Class:
- PartitionArray
- Method:
- positiveSum
- Parameters:
- int[]
- Returns:
- int[]
- Method signature:
- int[] positiveSum(int[] a)
- (be sure your method is public)
Constraints
- a will have between 1 and 500 elements, inclusive.
- All elements of a will be between -10^6 and 10^6, inclusive.
Examples
{3,-7,8}Returns: {1, 2 }The first example from the problem statement.{0,1,0,1,2}Returns: {4, 1 }Remember that you may return the description of any partition of the input sequence into one or more pieces, each with a positive sum. Each valid answer will be accepted.{-1,2,-3,4,-5}Returns: {-1 }{0}Returns: {-1 }
Back to all problems