Today's agenda
Sub
assays recap
Subarrays questions
4 contribution technique
Subarrays
Continuous Part is Subarsay
of an
array
E
Single element of an
array
Complete array is also a subarrayte
empty array xx
It 2 3,43 93,23
no reverse the
you can't
order in Suballay
Total no in array of length N
of Suballay an
G N Ceti
2
as 53 Lio 2 Jo to 553
Start othide start ist idn start 2nd idn
stogy
10 20 30
10 20 20 30 30 40 8
10 20 30 20 30 40 30 yo yo
1
10 20 30 40 20 30 40 50 3 N 2
10 20 30 40 50 4 N I
N
Total Count N t i i A 2 t1
Is a Cats
2
Q Given an a End Point Subarray from Es e
en assly 53 I 833
S I e 3
Us 3 I 8
for Lint i S ice itt
Point anti
[Link] OCH
a Given a elements point each and everySubaray
assay
En any 53 I 833
5 0 5 1 5 2 S 3
5 40,03 3 41,13 1 42,23 8
5 3 10 3 3 111,23 4 812,33
5 3 110,27 3 1 811,3
5 3 1820,33
void Pointsubarlays intarsia
sea Stt
foolints o
E
inte S een ett
for
7 c OCA 11s e Susanay
S C old int i S ice itt h
for
Point Carli
g
Tracing
int s Stt
for sea
o
inte S een ett E
for S o e o 3 5
116 e Subanay be I 5,3
Lint S ice s he
for 2 5,3 1
Point Carli he 3 5,3 1.8
3 S I e t 3
Q Given a
assay
elements Point each Subarray Sum
En assad 153 I 83
5 0 5 1 5 2 S 3
5 40,0375 41,13 3
3 a sis 843.33 18
53 10,1348 3 111,23 2 4 812,33
47
5 3 I 0,2777 a
10
5 3 1 820,33
415
void Pointsubarlays intarsia
int s Stt
for sea
o
inte S een ett C
for
7c OCA 11s e Subarray
S.c old finding S ice itt I
Sum Suntan i
3
Bint sum
I
g
I ideal
Prefin Sum idea
En assad 153 I 83
5 0 5 1 5 2 S 3
5 40,03 5 3 41 3 3 a 12 3 843.33 18
53 10,1348 3 111,23 2 4 812,33
47
5 3 110,2777 3 1 811,3
10
53
18293
Pfa 15 8 7 153
SumCi Psumfi D
j PSumCj
IPswedocode
void PointSubarlays int arfa
int PlumC PolfinsummCast
int s Stt
for s ere
o
int e S een ett E
for
Tc dig Ils es susarray
OCH
if Cs o h point Psumle 3
Sec OLD
else Point psumle PsumCs D
3
g
a Given arm elements return Sum all SubarraySums
of
e i 2 3
en asf 5 3 a 8
5 0 5 1 5 2 S 3
5 40,0315 3 41 3 3 a 132 843.33 8
5 3 10 3 78 3 111,23 2 a 84433
5 3 110,2777 3 1 811,35
10
5 3
18293 t
Ussum 64
void Pointsubarlays int assn
int PlumC Polfinsummiast
footings sane still
inte S een ett C
for
if if Cs
else
o
ans
hanseanst Psumfed
ant Psumle Psumes 17
g Point ans
Hidea2
arras 53 8
5 3 8
y't I I 4 8
5 3 I 3 1 8
5 3 I 8
Chars O
occ
and g 4 times
Us 5 4 20
a 2111 3 I 6 times
3 6218
a0212 I 7 6 times
1 6 6
an 133 8 7 4 times
Us 8 4 32
ans 64
assad Ls 3 8
É Ia Ia Is
ans Asolo no t of 3 ne Lasso 22
Car 3 23
Finding occurrence
on L j É 4 i i iz
s e
0 3 3
I 4 3
2 5 I
3 I
44 3 12 Subahays
en h 3 i i i i iz
s e
0 I 2 5 10 Suballays
1 2
general ai
en h 3 i i i i iz
No Occ No of valid s Cao of valid e
of
its
o Eta a
I
ite elements N H ix a
element
Total occ ith inder ite i
no
of of
IPSuedo code
int total sum int arak
int ans 20
int i ien it f f
for int occ
O
ite Cn i
S C Oct
return ans
Tracing e i 2 3
asf Ls 3 I 8
int ans o it
ien it f
for intint occ
iO
ite i
Occ 4 1
ans t Cocca anti
ans
as O A
9 p
A 8 4
3
0 20 18 6 A 32
return any
64
I
contribution technique
a number of Suballays with bounded maximum
Given an ad and two integers left andright Return
the number of Suballays Such that value of the maximum
element in that Suballay is in the range
array left sight
Ena an u L2 I 4 33 left2 Right 3
2 I 3
2 1 I 4 I
2 I 4 I 4
2 I 4
th ans 3
Mideast
the Sub and
create all alloys Calculate the man
Pick the valid once
Tc O a old a 063
I idea2 yep
art 9 i i t's j
e G R 8
Case r a ler R
yep
art 9 i i t's j
l G R 8
validstartingPoints o
case 2 an Cep L II as Cep Car
aged get
assfo 9 I 8 I j I it
1 6 R 8
validstartingPoints
Igel
last
er
greaterthanright element
indent 1
H
epp I
age
Case 3 an Cep K L
def
art 19 It I5 j
l G R 8
validstartingPoints valid Starting Points
no
of for
the element in the range
of C R just before the
Current element
IPSuedecode
int validsubarlay Carola int int
left right
int ans o
int egei o
int Pservalid count o
inter epcot eptt
for
o
Caroler r f
if Poervalidcounto
Toc O n ans ans t o
ege esta
SC OC 3
else asleep L 92 an EPICRK
ifans
ans Cep egesta
Poervalidcount ep
3 lgeitt
else 11 aster CL
ans i ans A Blu valid Count
3
tooling
def
int valid arrayCaronintleftintrightI
sub
int ans o
a g t's i i to
int egei o I ig
l G R8
for
Cine
is sit erase
ans o to 1 A2 3 A 3 3 3 to
It 2
ans anst o
ege esta
Poervalidconto
PruvalidCount I 0 I 2 3 01 2
else Carolee Lorancestry
if
ans ansCepegesta
3 done
Parvati epegeita
else isasoledcc
ans i ansa Bev
valid
count
3
Q man Sub
allay Sum LKadare'salgo
Given a elements calculate man Suballay
assay
Sum
End a 017 3 2 6 8 2 9 43
Gans 23
Enz a0177 3 2 4 I 3 4 33
Gans 8
I ideal
generate all Subassay Sum and find man out
of
them
TC off S C O Ca
Hideaz Kadare's algo
tretretretretrel sum
of all these
f ve ve tretre tre3 sum
of last three
1 cave
age
i
assai i s in ii so's
sum O 3 5 16 4 5
Sg
Ahs A 3 a g 16 16 16
11Psuedo Code
int Kadanes int area L
int sum og
int ans Integer Man VALUE
forcintiogiangitt I
[Link] OCA
if sum 2 031
S C 011 Sum Sunt anti
Sum an lil
g
ans math man Cans sum
return ans
forcintiogian itt h away j y I i i É
sum amiss ayy
gym 57016
Sum an lil
959
ans mathman Canssum
g
mm
sum 0 3
ans o I
assai i i s in ii so's
4
I
I
e i
16 20
16 20
