<prompt> Kwa kuzingatia n, igawanye iwe jumla ya k nambari kamili, ambapo k 2, na uongeze bidhaa ya nambari hizo kamili.Rudisha _kiwango cha juu zaidi cha bidhaa unayoweza kupata_.Mfano wa 1:Ingizo: n 2Pato: 1Maelezo: 2 1 1, 1 1 1.Mfano wa 2:Ingizo: n 10Pato: 36Maelezo: 10 3 3 4, 3 3 4 36.Vikwazo: 2 n 58  <response>: chatudef integer_breakn: ikiwa n 3: kurudi n - 1 bidhaa 1 wakati n 4: bidhaa 3 n 3 bidhaa ya kurudisha nmaelezoAlgorithm inatokana na ukweli kwamba uwekaji alama bora kwa nambari kamili n linajumuisha 3 nyingi iwezekanavyo, na labda 2 au 4. Ikiwa tuna sababu inayojumuisha 1 tano, tunaweza kuivunja kila wakati kuwa 2 mbili na a 3, ambayo ina bidhaa kubwa 2 2 3 1 1 1 1 1. Hii inamaanisha kuwa vipengele vilivyojumuishwa katika bidhaa ya mwisho hazitawahi kuwa ndogo kuliko 2.Suluhisho ni kutoa 3 mara kwa mara kutoka kwa nambari uliyopewa n na kuzidisha bidhaa kwa 3. Tukimaliza na n kuwa 2, 3, au 4 baada ya mchakato huu, tunazidisha bidhaa kwa n na kurudisha. hiyo.Suluhisho hili linaendesha katika ugumu wa wakati wa O n. 