我们可以知道，左边有一部分元素是用法则一处理，右边有一部分元素是用法则二处理，中间有一部分是用法则三处理。这里就涉及到了三部分的两个边界，这意味着我们可能要用N^2的复杂度来遍历这些边界并计算代价。本题有一个巧妙的解法，就是令dp1[i]表示[0:i]这些元素用法则一、三处理（即删除元素1）需要的最少代价；同理令dp2[i]表示[i:n-1]这些元素用法则二、三处理需要的最少代价。这样我们只需要遍历一个边界即可。
对于dp1[i]，我们需要根据s[i]是否是1来做不一样的决策. 如果s[i]本身是0，那么0不需要删除也就不需要增加额外的代价，故有dp1[i]=dp1[i-1].
如果s[i]是1，那么我们有两种方法：
- 如果元素i是按照法则一删除，那么意味着[0:i]都是逐个从左往右删除的，故有
dp1[i]=i+1. - 如果元素i是按照法则三删除，那么删除s[i]本身需要付出2的代价，在此之前，我们就可以复用dp1[i-1]，因为我们并不关心在元素i之前具体使用什么法则实现dp[i-1]的，无论法则一还是三，都不影响我用法则三来删除s[i]。
综上，我们有dp1[i] = min(i+1, dp[i-1]+2)
同理我们可以得到dp2[i]，那么最终答案就是找全局最大的dp`[i]+dp2[i+1].
本题就是要找两个分界点i和j，使得[0:i-1]这部分按照法则1删除，代价就是i; [j+1:n-1]这部分按照法则2删除，代价就是n-j-1; 中间部分按照法则3删除，代价是[i:j]之间的元素1的个数乘以2。
于是我们可以将本题转化为求解最小化的i + 2*(presum[j]-presum[i-1]) + n-j-1，其中presum[k]表示[0:k]区间内有多少个元素1.
将上式再转化一下，即min {(2*presum[j]-j) - (2*presum[i-1]-(i-1)) + n}. 很显然，我们构造新的数列nums[i]=2*presum[i]-i，即求min (arr[j] - arr[i-1]) + n, where i<j。注意特别地，i是可以取0的， 故arr[-1]需要取值为2*presum[-1]+1 = 1. 因此我们要在arr数组的最前端额外加上1.
另外，需要思考一下，如果全程只是法则1或者2，那么上述分析的[i:j]区间不存在，这意味着我们必须从左到右依次删去全部，故ret要有一个初始值就是n。