<prompt> Kwa kuzingatia n nambari kamili zisizo hasi zinazowakilisha ramani ya mwinuko ambapo upana wa kila upau ni 1, hesabu ni kiasi gani cha maji kinachoweza kunasa baada ya mvua kunyesha.Mfano wa 1:Ingizo: urefu 0,1,0,2,1,0,1,3,2,1,2,1Pato: 6Maelezo: Ramani ya mwinuko iliyo hapo juu sehemu nyeusi inawakilishwa na safu 0,1,0,2,1,0,1,3,2,1,2,1. Katika kesi hii, vitengo 6 vya maji ya mvua sehemu ya bluu vinanaswa.Mfano wa 2:Ingizo: urefu 4,2,0,3,2,5Pato: 9Vikwazo: n urefu.urefu 1 n 2 104 0 urefui 105  <response>: chatudef trapurefu: n len urefu kushoto, kulia, upeo_kushoto, upeo_kulia, maji 0, n - 1, 0, 0, 0 wakati kushoto kulia: ikiwa urefukushoto urefukulia: max_left maxmax_left, urefukushoto maji max_left - urefukushoto kushoto 1 kwingine: max_right maxmax_right, urefukulia maji max_right - urefukulia kulia - 1 kurudi majimaelezoKanuni hutumia mbinu ya viashiria viwili, kuanzisha viashiria vya kushoto na kulia hadi mwanzo na mwisho wa ramani ya mwinuko, mtawalia. Pia huanzisha viambajengo viwili maxLeft na maxRight ili kufuatilia urefu wa juu zaidi upande wa kushoto na kulia wa viashiria, pamoja na kigezo cha maji ili kuhifadhi maji yaliyonaswa.Algorithm inarudia kupitia ramani ya mwinuko hadi kielekezi cha kushoto kiwe chini ya kielekezi cha kulia. Katika kila marudio, inalinganisha maadili katika viashiria vyote viwili ili kuamua ni upande gani ni mfupi. Ikiwa thamani iliyo kwenye kielekezi cha kushoto ni chini ya au sawa na thamani iliyo kwenye kielekezi cha kulia, inamaanisha kwamba maji yanaweza kunaswa upande wa kushoto hadi urefu wa upau fupi. Kanuni ya kanuni husasisha maxLeft kwa urefu wa juu zaidi upande wa kushoto na kisha kuongeza maji yaliyonaswa ambayo ni tofauti kati ya urefu wa juu zaidi na urefu wa sasa kwenye kigeuzo cha maji. Kisha pointer ya kushoto inaongezwa. Ikiwa thamani iliyo kwenye kielekezi cha kulia ni ndogo, mantiki sawa inatumika kwa upande wa kulia na kielekezi cha kulia kinapunguzwa.Mchakato huu unarudiwa hadi kielekezi cha kushoto kisiwe chini ya kielekezi cha kulia, ambapo jumla ya maji yaliyonaswa huhesabiwa na kigeu cha maji kinarejeshwa. Algorithm hii ina ugumu wa wakati wa On na uchangamano wa nafasi ya O1 kwani hutumia tu nafasi ya ziada ya mara kwa mara. 