Greatest subsequential sum: Difference between revisions

Content added Content deleted
m (→‎{{header|AppleScript}}: Updated primitives – max and gt)
m (→‎JS Functional: (Adjusted type signature of main function))
Line 1,597: Line 1,597:


===Functional===
===Functional===
Linear approach – an accumulating fold over the input list.
Linear approach, deriving both list and sum in a single accumulating fold.


<lang JavaScript>(() => {
<lang JavaScript>(() => {


// maxSubseq :: [Int] -> [Int]
// maxSubseq :: [Int] -> (Int, [Int])
const maxSubseq = xs =>
const maxSubseq = xs =>
xs.reduce((tpl, x) => {
snd(xs.reduce((tpl, x) => {
const [m1, m2] = Array.from(tpl[0]),
const [m1, m2] = Array.from(fst(tpl)),
high = max(
high = max(
Tuple(0, []),
Tuple(0, []),
Tuple(m1 + x, m2.concat(x))
Tuple(m1 + x, m2.concat(x))
);
);
return Tuple(high, max(tpl[1], high));
return Tuple(high, max(snd(tpl), high));
}, Tuple(Tuple(0, []), Tuple(0, [])))[1][1];
}, Tuple(Tuple(0, []), Tuple(0, []))));




// TEST -----------------------------------------------
// TEST -----------------------------------------------
// main :: IO ()
// main :: IO ()
const main = () =>
const main = () => {
⚫
const mx = maxSubseq([-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]);
showLog(...ap([id, sum], [
showLog(snd(mx), fst(mx))

}
⚫
maxSubseq([-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1])

]));
// [3,5,6,-2,-1,4] -> 15
// [3,5,6,-2,-1,4] -> 15


Line 1,626: Line 1,624:
// GENERIC FUNCTIONS ----------------------------------
// GENERIC FUNCTIONS ----------------------------------


// ap (<*>) :: [(a -> b)] -> [a] -> [b]
// fst :: (a, b) -> a
const ap = (fs, xs) => //
const fst = tpl => tpl[0];
fs.reduce((a, f) => a.concat(
xs.reduce((a, x) => a.concat([f(x)]), [])
), []);


// gt :: Ord a => a -> a -> Bool
// gt :: Ord a => a -> a -> Bool
Line 1,637: Line 1,632:
x[0] > y[0]
x[0] > y[0]
) : (x > y);
) : (x > y);

// id :: a -> a
const id = x => x;


// max :: Ord a => a -> a -> a
// max :: Ord a => a -> a -> a
Line 1,652: Line 1,644:
);
);


// sum :: [Num] -> Num
// snd :: (a, b) -> b
const sum = xs => xs.reduce((a, x) => a + x, 0);
const snd = tpl => tpl[1];


// Tuple (,) :: a -> b -> (a, b)
// Tuple (,) :: a -> b -> (a, b)
Retrieved from "https://rosettacode.org/wiki/Greatest_subsequential_sum"