Happy Array
Problem :
practice
Tags: Dynamic Programming, Prefix sum.
Author: Shami.
Tester: Naman
There are multiple ways to look at this problem.
1.Longest Increasing Subsequence
A sequence (not necessarily contiguous) with leading 0s and (possibly) ending with 1s is essentially a weakly increasing subsequence. As such, we can compute the LIS for the array that will give you the answer.
This problem had weak testcases, which allowed O(N^2) LIS solutions to be accepted. However, LIS can be computed in O(Nlog(K)) as well.
2.For each 0, the longest length of happy array is, at least, number of 0s to the left (including itself) and number of 1s to the right. We can use prefix sums to compute the number of 1s at each index and use it to compute the longest possible happy array for each 0. Not using prefix sum array will cause this algorithm to degenerate to O(N^2), which is same as above.