URL

Longest Subarray of 1's After Deleting One Element - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/1493/main.fsx

open System

let longestSubarray (nums: int list) : int =
    let rec collectOnes nums i start acc =
        match nums with
        | [] ->
            match start with
            | Some(v) -> ((v, i - v) :: acc) |> List.rev
            | None -> acc |> List.rev
        | h :: t ->
            match start with
            | Some(v) ->
                if h = 1 then
                    collectOnes t (i + 1) start acc
                else
                    collectOnes t (i + 1) None ((v, i - v) :: acc)
            | None ->
                if h = 1 then
                    collectOnes t (i + 1) (Some(i)) acc
                else
                    collectOnes t (i + 1) None acc

    let rec longestSubarray' pairs (prevStart, prevLength) (ret: int) =
        match pairs with
        | [] -> ret
        | (start, length) :: t ->
            if prevStart + prevLength + 1 = start then
                longestSubarray' t (start, length) (Math.Max(ret, length + prevLength))
            else
                longestSubarray' t (start, length) (Math.Max(ret, length))

    let len = List.length nums
    let pairs = collectOnes nums 0 None []

    match pairs with
    | [] -> 0
    | (_, length) :: [] -> if len = length then len - 1 else length
    | prev :: t -> longestSubarray' t prev 0