如何用一行Linq实现1/-1数组中前缀和≥0的最长连续子数组提取

给定仅由1和-1组成的整数数组，找到最长的连续子数组，要求遍历该子数组的过程中累加计数器始终≥0，最终返回该子数组。
计算规则：初始计数器为0，累加元素值后如果结果小于0，就重置计数器，丢弃当前已统计的子数组重新开始统计。

输入输出示例 #

输入示例：

int[] arr = new int[] { -1, 1, -1, 1, 1, -1 };

输出示例：

Solve(new int[] { -1, 1, -1, 1, 1, -1 }); // => new int[] { 1, -1, 1, 1, -1 };

原迭代实现代码 #

public static List<int> Solve(int[] input)
{
   List<List<int>> compare = new List<List<int>>();
   List<int> temp = new List<int>();
   for(int i = 0, c = 0; i < input.Length; i++)
   {
       if(input[i] == 1)
       {
           c++;
           temp.Add(input[i]);
       }
       else if(input[i] == -1)
       {
           c--;
           if (c >= 0)
               temp.Add(input[i]);
           else
           {
              c = 0;
              compare.Add(temp);
              temp = new List<int>();
           }
       }
   }

   compare.Add(temp);
   return compare.OrderByDescending(x => x.Count).First();
}

测试用例参考 #

Solve(new int[] { -1, 1, -1, 1, 1, -1 }); // => new int[] { 1, -1, 1, 1, -1 };
Solve(new int[] { 1, 1, -1, -1, 1, 1 }); // => new int[] { 1, 1, -1, -1, 1, 1 };
Solve(new int[] { 1, -1, 1, -1, 1, -1, -1, 1, 1, 1 }); // => new int[] { 1, -1, 1, -1, 1, -1 };
Solve(new int[] { 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1, -1 });
// => new int[] { 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1 };
Solve(new int[] { -1, -1, -1 }); // => new int[] { };

一行LINQ实现 #

public static List<int> Solve(int[] input) => input.Aggregate(new { Counter = 0, Current = new List<int>(), Longest = new List<int>() }, (state, num) => { int newCounter = state.Counter + num; if (newCounter < 0) return new { Counter = 0, Current = new List<int>(), Longest = state.Current.Count > state.Longest.Count ? state.Current : state.Longest }; List<int> newCurrent = new List<int>(state.Current) { num }; return new { Counter = newCounter, Current = newCurrent, Longest = newCurrent.Count > state.Longest.Count ? newCurrent : state.Longest }; }, finalState => finalState.Current.Count > finalState.Longest.Count ? finalState.Current : finalState.Longest);

该实现通过Aggregate方法维护三个遍历状态：当前累加计数器值、当前正在统计的子数组、已经找到的最长符合要求的子数组，遍历完成后直接返回最长子数组，所有测试用例均可正常通过。

内容的提问来源于stack exchange，提问作者Plus