# 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:

- : 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 . - : abbreviation of .

Based on such notations, the final answer can be descibed as: for all position , find out the longest interval `[h, i]`

, such that and . And the answer of this problem is .

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

For a specific position , define `dp[i]`

as the length of longest **interval** ending with and . Then the final answer should be the largest of `dp[i]`

, where .

For a specifice position , if , then `dp[i]`

equals .

If , `dp[i]`

is the length of **longest interval** `[h, i]`

, which satisfying conditions: and .

As `[0, i] = [0, h-1] + [h, i]`

, we have , i.e. , which is equivalent to . This tells us: if we can find interval satisfying above conditions, must be strictly greater than .

Suppose `[k, i]`

is the longest interval we’re searching for, we propose a statement that: , i.e. only less than 1 comparing to , which can’t become a much smaller number.

**Proof by contradiction**: if can be smaller, as the change of each is continuous with “1” difference, there must be a position such that and . 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]`

, must be equal to . 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 equals , and we choose the smallest position as answer.

Specifically, we can use a map to store each pre-interval sum as *key*, and its correpsonding position 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 . If it holds, we get a candidate answer . 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;
}
```