将Java最大非重叠递增子序列代码转Haskell遇困求助

Hey there! I totally get that switching from Java's imperative, state-heavy style to Haskell's functional paradigm can feel overwhelming when you're still learning—especially with dynamic programming problems like this one. Let's break this down step by step, starting with core concepts and then building an idiomatic Haskell solution that aligns with the Java logic you started with.

First, Let's Clarify the Problem #

From your Java code snippets (with memo, lis, and lmemo arrays), it looks like you're tackling the maximum non-overlapping increasing subsequences problem—likely aiming to either:

• Find the maximum number of non-overlapping increasing subsequences (no shared elements), or
• Maximize the total length of such non-overlapping subsequences.

We'll focus on the latter (total length maximization) since it's the more complex case, and show how to map Java's stateful DP to Haskell's pure functions.

Step 1: Input Handling (Replace Java's Scanner/String Splitting) #

In Java, you're reading input as a string, splitting it into an array of integers. In Haskell, we can do this with pure I/O functions:

import Data.List (splitOn)
import Data.Map (Map)
import qualified Data.Map as Map

-- Read input line, split into a list of integers
readInput :: IO [Int]
readInput = do
  inputLine <- getLine
  return $ map read (splitOn " " inputLine)

This replaces Java's String[] arrIn and int[] nums with a Haskell [Int] (immutable list of integers).

Step 2: Porting the Dynamic Programming Logic #

Your Java code uses memoization arrays (memo, lis) to cache intermediate results. In Haskell, we avoid mutable arrays—instead, we use pure memoization with a Map (or Vector for faster access) to store computed states.

Here's a refined, efficient approach that tracks the best possible total length for subsequences ending at each value (similar to your Java lis array):

import Data.List (foldl')

-- Compute maximum total length of non-overlapping increasing subsequences
maxNonOverlappingLISLength :: [Int] -> Int
maxNonOverlappingLISLength nums = snd $ foldl' updateState (Map.empty, 0) nums
  where
    -- State is (map: endValue -> max total length up to this point, global maximum)
    updateState :: (Map Int Int, Int) -> Int -> (Map Int Int, Int)
    updateState (endMap, globalMax) x =
      -- Find the longest valid subsequence we can append x to
      let bestPrev = maybe 0 snd (Map.lookupLT x endMap)
          -- New length if we take x (either start a new subsequence or append to an existing one)
          newLen = bestPrev + 1
          -- Update the map to keep the maximum length for subsequences ending at x
          newEndMap = Map.insertWith max x newLen endMap
          -- Update the global maximum total length
          newGlobalMax = max globalMax newLen
      in (newEndMap, newGlobalMax)

This uses a left fold to iterate through the array, updating an immutable state (a map and global max) instead of modifying arrays like in Java—this is far more idiomatic for Haskell.

Step 3: Putting It All Together #

Here's a complete program that reads input and outputs the result:

import Data.List (foldl', splitOn)
import Data.Map (Map)
import qualified Data.Map as Map

readInput :: IO [Int]
readInput = do
  inputLine <- getLine
  return $ map read (splitOn " " inputLine)

maxNonOverlappingLISLength :: [Int] -> Int
maxNonOverlappingLISLength nums = snd $ foldl' updateState (Map.empty, 0) nums
  where
    updateState :: (Map Int Int, Int) -> Int -> (Map Int Int, Int)
    updateState (endMap, globalMax) x =
      let bestPrev = maybe 0 snd (Map.lookupLT x endMap)
          newLen = bestPrev + 1
          newEndMap = Map.insertWith max x newLen endMap
          newGlobalMax = max globalMax newLen
      in (newEndMap, newGlobalMax)

main :: IO ()
main = do
  nums <- readInput
  putStrLn $ "Maximum total length of non-overlapping increasing subsequences: " ++ show (maxNonOverlappingLISLength nums)

Key Differences from Java #

• No mutable state: Instead of modifying memo or lis arrays, we use immutable maps and fold over the input to build up results.
• Pure functions: All logic is in pure functions (no side effects), which aligns with Haskell's functional paradigm.
• Memoization via Maps: Instead of array indexes, we use a Map to cache the best possible length for subsequences ending at each value—this is more flexible than fixed-size arrays.

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