Advertisement
MaxObznyi

subsegment with max sum

Jun 25th, 2022
887
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct node {
  2.     int sum_max, suff, pref, sum;
  3. };
  4.  
  5. node combine(node tl, node tr) {
  6.     node res;
  7.     res.sum = tl.sum + tr.sum;
  8.     res.pref = max(tl.pref, tl.sum + tr.pref);
  9.     res.suff = max(tr.suff, tr.sum + tl.suff);
  10.     res.sum_max = max({
  11.         tl.sum_max,
  12.         tr.sum_max,
  13.         tl.suff + tr.pref;
  14.     });
  15.     return res;
  16. }
  17.  
Advertisement
RAW Paste Data Copied
Advertisement