LeetCode 1124

As we need to compare the counts of tiring days and non-tiring days, we can use number 1 to indicate tiring day and -1 to indicate non-tiring day. Then, the sum of interval represented by -1/1 will reveal if tiring days are strictly greater than non-tiring days.

Then the goal of this problem becomes: find the longest interval such that the sum of this interval will be strictly greater than 0, and the length of this interval is the final answer.

First, let’s introduce some definitions:

• $S_{(i, j)}$: the sum of interval [i, j] represented by -1/1 described above. The index of interval starts from 0. For example, if the interval is [1, -1, -1, 1], then $S_{(1, 3)} = -1 + (-1) + 1 = -1$.
• $S_i$: abbreviation of $S_{(0, i)}$.

Based on such notations, the final answer can be descibed as: for all position $i$, find out the longest interval [h, i], such that $0 \le h \lt i$ and $S_{(h, i)} \gt 0$. And the answer of this problem is $(i - h + 1)$ .

Apparently, this can be solved by pre-solved sub-problem with dynamic programming method.

For a specific position $i$, define dp[i] as the length of longest interval ending with $i$ and $S_i \gt 0$. Then the final answer should be the largest of dp[i], where $0 \le i \lt input\_arr\_length$.

For a specifice position $i$, if $S_i \gt0$, then dp[i] equals $(i + 1)$.

If $S_i \le 0$, dp[i] is the length of longest interval [h, i], which satisfying conditions: $0\le h \lt i$ and $S_{(h, i)} \gt 0$.

As [0, i] = [0, h-1] + [h, i] , we have $S_{i}=S_{h-1} + S_{(h, i)}$, i.e. $S_{i} - S_{h-1} = S_{(h,i)} \gt 0$, which is equivalent to $S_i \gt S_{h-1}$. This tells us: if we can find interval satisfying above conditions, $S_i$ must be strictly greater than $S_{h-1}$.

Suppose [k, i] is the longest interval we’re searching for, we propose a statement that: $S_{(k-1)} = S_i - 1$, i.e. $S_{k-1}$ only less than 1 comparing to $S_i$, which can’t become a much smaller number.

Proof by contradiction: if $S_{k-1}$ can be smaller, as the change of each $S_i$ is continuous with “1” difference, there must be a position $j$ such that $j \lt (k-1)$ and $S_j = S_{i} - 1$. Apparently, [j, i] is a interval longer than [k, i], which contradicts the longest assumption that [k, j] is the longest interval satisfying conditions.

Thus, if there exising longest interval [k, i], $S_{k-1}$ must be equal to $S_i - 1$. If there’s another pre-positions satisfying this equation, we should choose the smallest position to get the longest interval. So we only need to check if there’s a interval [0, k-1] such that $S_{k-1}$ equals $S_i - 1$, and we choose the smallest position $k$ as answer.

Specifically, we can use a map to store each pre-interval sum $S_i$ as key, and its correpsonding position $i$ as value. We should add (key, val) pair of this map only when the key hasn’t been put into this map, which ensure it stores the smallest position of each sum value. Then, we only need to check if this map holds the key $S_i -1$. If it holds, we get a candidate answer $(i - k + 1)$. Otherwise, it just shows there’s no interval such that the sum of [k, i] is greater than 0.

private boolean isTiringDay(int work) {
    return (work > 8);
}

public int longestWPI(int[] hours) {
    if (null == hours) { return 0; }
    int res = 0, sum = 0;
    Map<Integer, Integer> sumMap = new HashMap<>();

    for (int i = 0; i < hours.length; i++) {
        sum += isTiringDay(hours[i]) ? 1 : -1;

        if (sum > 0) {
            res = i + 1;
        } else {
            sumMap.putIfAbsent(sum, i);
            if (sumMap.containsKey(sum-1)) {
                res = Math.max(res, i - sumMap.get(sum-1));
            }
        }
    }

    return res;
}