Array Break

Problem Overview

• Count the number of perfect breaks of an array arr into b and c where b is non-decreasing, c is non-increasing, b[i] ≥ 0, c[i] ≥ 0, and b[i] + c[i] = arr[i] for all i.
• Input: arr with 1 ≤ n ≤ 3000 and 1 ≤ arr[i] ≤ 3000; Output: count modulo 1,000,000,007.
• Domain: array decomposition under monotonic constraints, relevant to combinatorics and data partitioning.
• This coding interview problem is a common interview question from Deshaw interviews.