×

# HAPPYARR - Editorial

 0 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. asked 12 Jan, 15:49 0★mmmreddy 12●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,033
×199