• Non ci sono risultati.

Sottovettore di somma massimale

N/A
N/A
Protected

Academic year: 2021

Condividi "Sottovettore di somma massimale"

Copied!
43
0
0

Testo completo

(1)

Sottovettore di somma massimale

• Proviamo ad adottare un approccio brute force

• Calcoliamo la somma di ogni possibile sottovettore che termina in A[i]

• Dopo, calcoliamo la soma di ogni possibile sottovettore che termina in A[i+1]

• Il valore massimo tra tutte le somme identifica il nostro sottovettore di interesse

1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

(2)

Sottovettore di somma massimale

1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

-3 10 -3 -3 10 -3 4 -3 10 -3

3 4 -3 10 -3

-1 3 4 -3 10 -3

3 -1 3 4 -3 10 -3

2 3 -1 3 4 -3 10 -3

-8 2 3 -1 3 4 -3 10 -3

4 -8 2 3 -1 3 4 -3 10 -3

1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

2 -3 2

10 -3 2

-3 10 -3 2

4 -3 10 -3 2

3 4 -3 10 -3 2

-1 3 4 -3 10 -3 2

3 -1 3 4 -3 10 -3 2

2 3 -1 3 4 -3 10 -3 2

-8 2 3 -1 3 4 -3 10 -3 2

4 -8 2 3 -1 3 4 -3 10 -3 2

(3)

Sottovettore di somma massimale

‣ Concentriamoci sul terzo elemento del vettore

‣ Il “massimo locale” è 8, corrispondente al

sottovettore dall'indice 0 all'indice 2

1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

4

3 4

1 3 4

4 7 8

somme

(4)

Sottovettore di somma massimale

‣ Concentriamoci sul quarto elemento del vettore

‣ La parte gialla corrisponde all'insieme di vettori

considerato nel caso precedente

‣ Se conosciamo già quelle somme, non è necessario ricalcolarle

‣ Se ci confrontiamo con il massimo precedente e troviamo uno zero (o un

1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

-4 -1 0

somme

-8 4 -8

3 4 -8

1 3 4 -8

-8

(5)

Programmazione dinamica

• Viene tenuta traccia di quanto calcolato fino ad un certo punto di esecuzione dell'algoritmo

• Sia maxHere[i] il valore del sottovettore di somma massima che termina in posizione A[i]

Programmazione dinamica

ﷻࣿ�[ ] = 0 < 0

max ﷻࣿ�[ − 1] + [ ], 0 ≥ 0

(6)

Programmazione dinamica (Kadane’s Algorithm)

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere

maxSoFar

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

(7)

Programmazione dinamica (Kadane’s Algorithm)

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere

maxSoFar

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

(8)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 0

maxSoFar 0

(9)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 0

maxSoFar 0

i=0

(10)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1

maxSoFar 0

i=0

(11)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1

maxSoFar 1

i=0

(12)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 1

maxSoFar 1 1

i=1

(13)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4

maxSoFar 1 1

i=1

(14)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4

maxSoFar 1 4

i=1

(15)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

Programmazione dinamica (Kadane’s Algorithm)

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 4

maxSoFar 1 4 4

i=2

(16)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

Programmazione dinamica (Kadane’s Algorithm)

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8

maxSoFar 1 4 1

i=2

(17)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8

maxSoFar 1 4 8

i=2

(18)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 8

maxSoFar 1 4 8 8

i=3

(19)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0

maxSoFar 1 4 8 8

i=3

(20)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0

maxSoFar 1 4 8 8

i=3

(21)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 0

maxSoFar 1 4 8 8 8

i=4

(22)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2

maxSoFar 1 4 8 8 8

i=4

(23)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 2

maxSoFar 1 4 8 8 8 8

i=5

(24)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 5

maxSoFar 1 4 8 8 8 8

i=5

(25)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 5

maxSoFar 1 4 8 8 8 8 8

i=6

(26)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4

maxSoFar 1 4 8 8 8 8 8

i=6

(27)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4 4

maxSoFar 1 4 8 8 8 8 8 8

i=7

(28)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4 7

maxSoFar 1 4 8 8 8 8 8 8

i=7

(29)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4 7 7

maxSoFar 1 4 8 8 8 8 8 8 8

i=8

(30)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4 7 11

maxSoFar 1 4 8 8 8 8 8 8 8

i=8

(31)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4 7 11

maxSoFar 1 4 8 8 8 8 8 8 11

i=8

(32)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 5 4 7 11 11

maxSoFar 1 4 8 8 8 8 8 8 11 11

i=9

(33)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4 7 11 8

maxSoFar 1 4 8 8 8 8 8 8 11 11

i=9

(34)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4 7 11 8 8

maxSoFar 1 4 8 8 8 8 8 8 11 11 11

i=10

(35)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4 7 11 8 18

maxSoFar 1 4 8 8 8 8 8 8 11 11 11

i=10

(36)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2

maxHere 1 4 8 0 2 5 4 7 11 8 18

maxSoFar 1 4 8 8 8 8 8 8 11 11 18

i=10

(37)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 5 4 7 11 8 18 18 maxSoFar 1 4 8 8 8 8 8 8 11 11 18 18

i=11

(38)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 5 4 7 11 8 18 15 maxSoFar 1 4 8 8 8 8 8 8 11 11 18 18

i=11

(39)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 5 4 7 11 8 18 15 15 maxSoFar 1 4 8 8 8 8 8 8 11 11 18 18 18

i=12

(40)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 5 4 7 11 8 18 15 17 maxSoFar 1 4 8 8 8 8 8 8 11 11 18 18 18

i=12

(41)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 5 4 7 11 8 18 15 17 maxSoFar 1 4 8 8 8 8 8 8 11 11 18 18 18

(42)

Programmazione dinamica (Kadane’s Algorithm)

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 5 4 7 11 8 18 15 17 maxSoFar 1 4 8 8 8 8 8 8 11 11 18 18 18

(43)

Programmazione dinamica (Kadane’s Algorithm)

A 1 3 4 -8 2 3 -1 3 4 -3 10 -3 2 maxHere 1 4 8 0 2 5 4 7 11 8 18 15 17 maxSoFar 1 4 8 8 8 8 8 8 11 11 18 18 18

def maxsum4(A):

maxSoFar = 0 # Maximum found so far

maxHere = 0 # Maximum slice ending at the current pos

start = end = 0 # Start, end of the maximal slice found so far last = 0 # Beginning of the maximal slice ending here for i in range(0, len(A)):

maxHere = maxHere + A[i]

if maxHere <= 0:

maxHere = 0 last = i+1

if maxHere > maxSoFar:

maxSoFar = maxHere

Riferimenti

Documenti correlati

Si innesca un ‘ciclo’ di attivazioni, non esplicitamente realizzato con strutture cicliche, dovuto alle susseguenti attivazioni che il sottoprogramma fa a se stesso (se

• Dividere il gruppo rimasto in tre sottogruppi e applicare di nuovo il procedimento finché i sottogruppi contengano una sola pallina: l’ultima pesata indicherà quale delle

Per sistemare le arance da mettere in vetrina e da vendere, il fruttivendolo Renato ha a sua disposizione dei vassoi che contengono 12 arance oppure altri vassoi più grandi che ne

• Per vincere dovete continuare a lanciare i dadi finché non &#34;fate il punteggio“ (ovvero ottenete nuovamente lo stesso valore).. Se in questa seconda fase lanciate un sette

Per dimostrare che in alcuni casi la legge del valore estremo EV1 non è adeguata a descrivere le scie degli estremi idrologici, si può far ricorso ad un test molto semplice, nel

Per dimostrare che in alcuni casi la legge del valore estremo EV1 non è adeguata a descrivere le scie degli estremi idrologici, si può far ricorso ad un test molto semplice, nel

Se il periodo è l’anno, questa è una rendita annuale di durata cinque anni, quindi è costituita da cinque rate posticipate L’inizio della rendita è oggi (anno 0) la fine

di modi di scrivere n come somma di 4 quadrati di