Problemi 21

Kërkesa

Një byrektore do zhvendoset nga qyteti A në qytetin B në një nga N ditët e ardhshme (të numëruara nga 1 deri në N). Ajo mund të zhvendoset brenda natës, ose para ditës 1, ose pas ditës N, ose në ndonjë nga netët midis tyre. I zoti do që ta zgjedhë natën e zhvendosjes në mënyrë të tillë që fitimi të jetë sa më i madh. Duke ditur fitimin që mund të nxirret në secilën nga ditët, në secilin qytet, sa është fitimi më i madh që mund të nxjerrë byrektorja në këto N ditë?

Referenca: https://www.codechef.com/LTIME71B/problems/FASTFOOD

Shembull

$ cat input.txt
3
3
2 3 2
10 3 4
4
7 5 3 4
2 3 1 3
2
10 1
1 10

$ python3 prog.py < input.txt
17
19
20

Jepet numri i ditëve N, dhe në dy rreshtat pasardhës jepen fitimet për secilën nga këto ditë në qytetet A dhe B.

Në rastin e parë fitimi më i madh merret nqs lëvizja bëhet para ditës së parë.

Në rastin e dytë fitimi më i madh merret nqs lëvizja bëhet pas ditës së fundit.

Në rastin e tretë fitimi më i madh merret nqs lëvizja bëhet pas ditës së parë.

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    max_p = sum(B)
    for i in range(n+1):
        p = sum(A[:i]) + sum(B[i:])
        if p > max_p:
            max_p = p
    print(max_p)

Koha e rendit \(O(N^2)\)

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    p = sum(B)
    max_p = p
    for i in range(n):
        p += A[i]
        p -= B[i]
        if p > max_p:
            max_p = p
    print(max_p)

Koha e rendit \(O(N)\)