algorithm - 返回数组中最多的元素个数 "expensive"

Question

我最近偶然发现了一个有趣的问题，我想知道我的解决方案是否是最优的。

You are given an array of zeros and ones. The goal is to return the amount zeros and the amount of ones in the most expensive sub-array.

The cost of an array is the amount of 1s divided by amount of 0s. In case there are no zeros in the sub-array, the cost is zero.

1. 起初我尝试了暴力破解，但是对于一个包含 10,000 个元素的数组，它太慢了，而且我用完了内存。

2. 我的第二个想法不是创建那些子数组，而是记住子数组的开始和结束。这样我节省了很多内存，但复杂度仍然是 O(n²)。

3. 我想到的最终解决方案是 O(n)。它是这样的:

   从数组的开头开始，对于每个元素，计算子数组的代价，从1开始，到当前索引结束。所以我们将从一个由第一个元素组成的子数组开始，然后是第一个和第二个等等。因为我们唯一需要计算成本的是子数组中 1 和 0 的数量，我可以找到子阵列的最佳末端。

   第二步是从第一步的子数组的末尾开始，重复同样的操作找到最优的开始。这样我就确信整个阵列中没有更好的组合。

   这个解决方案是否正确？如果不是，是否有反例可以证明这个解决方案是错误的？

编辑

为清楚起见:假设我们的输入数组是 0101。有 10 个子数组:0,1,0,1,01,10,01,010,101 和 0101。

因为 101 是最昂贵的子阵列，所以最昂贵的子阵列的成本为 2。所以算法应该返回 1,2

编辑2

还有一件事我忘记了，如果 2 个子数组具有相同的成本，则越长的子数组“越贵”。

Answer 1

让我为我的假设勾勒出一个证明:

(a = 整个数组，*=零个或多个，+=一个或多个，{n}=恰好 n)

案例 a=0* 和 a=1+ : c=0

案例 a=01+ 和 a=1+0 :符合 1*0{1,2}1*，a是最优的

For the normal case, a contains one or more 0s and 1s.
This means there is some optimum sub-array of non-zero cost.
(S) Assume s is an optimum sub-array of a.
It contains one or more zeros. (Otherwise its cost would be zero).
(T) Let t be the longest `1*0{1,2}+1*` sequence within s 
(and among the equally long the one with with most 1s).
(Note: There is always one such, e.g. `10` or `01`.)
Let N be the number of 1s in t.
Now, we prove that always t = s.
By showing it is not possible to add adjacent parts of s to t if (S).
(E) Assume t shorter than s.
We cannot add 1s at either side, otherwise not (T).
For each 0 we add from s, we have to add at least N more 1s 
later to get at least the same cost as our `1*0+1*`.
This means: We have to add at least one run of N 1s.
If we add some run of N+1, N+2 ... somewhere than not (T).
If we add consecutive zeros, we need to compensate 
with longer runs of 1s, thus not (T).
This leaves us with the only option of adding single zeors and runs of N 1s each.
This would give (symmetry) `1{n}*0{1,2}1{m}01{n+m}...`
If m>0 then `1{m}01{n+m}` is longer than `1{n}0{1,2}1{m}`, thus not (T).
If m=0 then we get `1{n}001{n}`, thus not (T).
So assumption (E) must be wrong.

结论:最优子数组必须符合1*0{1,2}1*。

根据我上一条评论(1*01* 或 1*001*)中的假设，这是我在 Java 中的 O(n) impl:

public class Q19596345 {
    public static void main(String[] args) {
        try {
            String array = "0101001110111100111111001111110";
            System.out.println("array=" + array);
            SubArray current = new SubArray();
            current.array = array;
            SubArray best = (SubArray) current.clone();
            for (int i = 0; i < array.length(); i++) {
                current.accept(array.charAt(i));
                SubArray candidate = (SubArray) current.clone();
                candidate.trim();
                if (candidate.cost() > best.cost()) {
                    best = candidate;
                    System.out.println("better: " + candidate);
                }
            }
            System.out.println("best: " + best);
        } catch (Exception ex) { ex.printStackTrace(System.err); }
    }
    static class SubArray implements Cloneable {
        String array;
        int start, leftOnes, zeros, rightOnes;

        // optimize 1*0*1* by cutting
        void trim() {
            if (zeros > 1) {
                if (leftOnes < rightOnes) {
                    start += leftOnes + (zeros - 1);
                    leftOnes = 0;
                    zeros = 1;
                } else if (leftOnes > rightOnes) {
                    zeros = 1;
                    rightOnes = 0;
                }
            }
        }

        double cost() {
            if (zeros == 0) return 0;
            else return (leftOnes + rightOnes) / (double) zeros + 
                (leftOnes + zeros + rightOnes) * 0.00001;
        }
        void accept(char c) {
            if (c == '1') {
                if (zeros == 0) leftOnes++;
                else rightOnes++;
            } else {
                if (rightOnes > 0) {
                    start += leftOnes + zeros;
                    leftOnes = rightOnes;
                    zeros = 0;
                    rightOnes = 0;
                }
                zeros++;
            }
        }
        public Object clone() throws CloneNotSupportedException { return super.clone(); }
        public String toString() { return String.format("%s at %d with cost %.3f with zeros,ones=%d,%d", 
            array.substring(start, start + leftOnes + zeros + rightOnes), start, cost(), zeros, leftOnes + rightOnes);
        }
    }
}