using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode.QuestionBank.Question1124
{
    public class Solution1124_2 : Interface1124
    {
        /// <summary>
        /// 前缀和
        /// 1. 预处理前缀和数组，例如
        ///       索引：      0   1   2   3   4   5   6   7   8   9
        ///     原数组：[     5,  6,  9,  9,  9,  6,  0,  6,  6,  9]
        ///          1：[    -1, -1,  1,  1,  1, -1, -1, -1, -1,  1]
        ///     前缀和：[0,  -1, -2, -1,  0,  1,  0, -1, -2, -3, -2]
        ///     这样使用前缀和可以O(1)的时间得出子数组是否满足结果的要求
        /// 2. 使用双指针找出最大的解
        ///     [0,  -1, -2, -1,  0,  1,  0, -1, -2, -3, -2]
        ///      l                    r               <-- r   // 第1轮
        ///           l                   r           <-- r   // 第2轮
        ///               l                   r       <-- r   // 第3轮
        ///                   l                               // 第4轮，这一轮不用查找，因为左指针变大了，结果一定比上一轮小
        ///                       ... ...
        /// </summary>
        /// <param name="hours"></param>
        /// <returns></returns>
        public int LongestWPI(int[] hours)
        {
            int len = hours.Length;
            int[] precnt = new int[len + 1];
            for (int i = 0; i < len; i++) precnt[i + 1] = precnt[i] + (hours[i] > 8 ? 1 : -1);

            int result = 0, left = 0, right = len;
            while (right - left > result)
            {
                for (int i = right; i >= left; i--)
                {
                    if (precnt[i] > precnt[left])
                    {
                        result = Math.Max(result, i - left); break;
                    }
                }
                while (++left <= len && precnt[left] >= precnt[left - 1]) ;
                right = len;
            }

            return result;
        }
    }
}
