package Ġle et code . kotlin . dp Ċ Ċ /** Ċ Ġ* Ġf ( n ) Ġ- ĠMaximum Ġsum Ġending Ġat Ġindex Ġn Ċ Ġ* Ġmax So Far Ġ- ĠMax Ġsum Ġfound Ġso Ġfar Ċ Ġ* ĠRelation : Ċ Ġ* Ġf ( n ) Ġ= ĠMAX ( f ( n - 1 ) Ġ+ Ġarr [ n ], Ġarr [ n ]]) Ċ Ġ* ĠFor Ġevery Ġiteration Ġupdate Ġmax So Far Ġfound , Ġand Ġat Ġlast Ġreturn Ġit . Ċ Ġ*/ Ċ Ċ // ĠTop - down Ġapproach Ġusing Ġmemo ization Ċ // ĠStack Overflow Error Ġfor Ġbig Ġsize Ġarray , Ġbut Ġworks Ġfor Ġsmaller Ġarray Ġsize Ċ Ċ private Ġclass ĠSolution Ġ{ ĊĠĠĠ Ġvar Ġmax So Far Ġ= Ġ 0 ĊĠĠĠ Ġfun Ġmax Sub Array ( arr : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġmax So Far Ġ= Ġarr [ arr . last Index ] ĊĠĠĠĠĠĠĠ Ġmax Ending At ( arr . last Index , Ġarr ) ĊĠĠĠĠĠĠĠ Ġreturn Ġmax So Far ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġmax Ending At ( n : ĠInt , Ġarr : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( n Ġ< Ġ 0 ) Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġmax Here Ġ= Ġmax Of ( max Ending At ( n Ġ- Ġ 1 , Ġarr ) Ġ+ Ġarr [ n ], Ġarr [ n ]) ĊĠĠĠĠĠĠĠ Ġmax So Far Ġ= Ġmax Of ( max So Far , Ġmax Here ) ĊĠĠĠĠĠĠĠ Ġreturn Ġmax Here ĊĠĠĠ Ġ} Ċ } Ċ Ċ // ĠBottom - up Ġapproach Ġusing Ġtab ulation Ċ private Ġfun Ġmax Sub Array 2 ( arr : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠ Ġvar Ġmax So Far Ġ= Ġarr [ 0 ] ĊĠĠĠ Ġvar Ġmax Ending Here Ġ= Ġarr [ 0 ] ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 1 .. arr . last Index ) Ġ{ ĊĠĠĠĠĠĠĠ Ġmax Ending Here Ġ= Ġmax Of ( max Ending Here Ġ+ Ġarr [ i ], Ġarr [ i ]) ĊĠĠĠĠĠĠĠ Ġmax So Far Ġ= Ġmax Of ( max So Far , Ġmax Ending Here ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġmax So Far Ċ } Ċ