โปรแกรมหาค่า Index k ใหญ่สุดของลิสต์ใน Python

กำหนดค่า n, total, k พิจารณาลิสต์ขนาด n ที่ผลรวมเท่ากับ total และความต่างสัมบูรณ์ระหว่างสมาชิกติดกัน ≤ 1 หาค่าสูงสุดที่ Index k ของลิสต์ดังกล่าว

ตัวอย่าง: n=5 total=15 k=3 → Output: 4 ลิสต์ที่เป็นไปได้ [3,2,3,4,3] ค่าสูงสุดที่ Index 3 คือ 4

ขั้นตอนการแก้ปัญหา

x := 0
Loop: a = k+1, s = (x + x - a + 1) * floor(a/2), a = n-k, s += (x + x - a + 1) * floor(a/2), s -= x
ถ้า s > total: Break
x += 1
Return x - 1

ตัวอย่างโค้ด Python

def solve(n, total, k): 
    x = 0 
    while 1: 
        a = k + 1 
        s = (x + x - a + 1) * a // 2 
        a = n - k 
        s += (x + x - a + 1) * a // 2 
        s -= x 
        if s > total: 
            break 
        x += 1 
    return x - 1 

n = 5 
total = 15 
k = 3 
print(solve(n, total, k))

Input

5, 15, 3