1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminè sou: Entèvyou teknik]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Inivèsite Harvard]

3
00:00:04,630 --> 00:00:08,910
[Sa a se CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hi tout moun, mwen Kenny. Se mwen menm kounye a yon jinyò syans etidye òdinatè.

5
00:00:12,420 --> 00:00:17,310
Mwen se yon ansyen CS tf, ak mwen swete mwen te gen sa a lè m 'te yon underclassman,

6
00:00:17,310 --> 00:00:19,380
ak Se poutèt sa mwen bay sa a seminè.

7
00:00:19,380 --> 00:00:21,370
Se konsa, mwen espere ou jwi li.

8
00:00:21,370 --> 00:00:23,470
Sa a seminè se sou entèvyou teknik,

9
00:00:23,470 --> 00:00:26,650
ak tout resous mwen ka jwenn nan lyen sa a,

10
00:00:26,650 --> 00:00:32,350
lyen sa a dwa isit la, yon koup la resous.

11
00:00:32,350 --> 00:00:36,550
Se konsa, mwen te fè yon lis de pwoblèm, aktyèlman, byen yon pwoblèm kèk.

12
00:00:36,550 --> 00:00:40,800
Epitou yon jeneral resous paj kote nou ka jwenn konsèy

13
00:00:40,800 --> 00:00:42,870
sou ki jan pou prepare pou yon entèvyou,

14
00:00:42,870 --> 00:00:46,470
konsèy sou sa ou ta dwe fè pandan yon entèvyou reyèl,

15
00:00:46,470 --> 00:00:51,910
kòm byen ke ki jan yo apwòch pwoblèm ak resous pou referans nan lavni.

16
00:00:51,910 --> 00:00:53,980
Li nan tout sou entènèt.

17
00:00:53,980 --> 00:00:58,290
Ak jis prefas sa a seminè-a, yon avètisman,

18
00:00:58,290 --> 00:01:00,690
tankou sa a pa ta dwe - preparasyon pou antrevi ou

19
00:01:00,690 --> 00:01:02,800
pa ta dwe limite a sa sèlman lis sa a.

20
00:01:02,800 --> 00:01:04,750
Sa a se sèlman vle di ke yo gen yon gid,

21
00:01:04,750 --> 00:01:08,890
epi ou ta dwe definitivman pran tout bagay sa m 'di ak yon grenn sèl,

22
00:01:08,890 --> 00:01:14,620
men tou sèvi ak tout bagay mwen itilize yo ede w nan preparasyon entèvyou w la.

23
00:01:14,620 --> 00:01:16,400
>> Mwen pral ale pi vit nan glisad kap vini yo

24
00:01:16,400 --> 00:01:18,650
pou nou ka jwenn yo etid ka yo reyèl.

25
00:01:18,650 --> 00:01:23,630
Estrikti a nan yon entèvyou pou yon postion jeni lojisyèl,

26
00:01:23,630 --> 00:01:26,320
tipikman li se 30 a 45 minit,

27
00:01:26,320 --> 00:01:29,810
jij miltip, depann sou konpayi an.

28
00:01:29,810 --> 00:01:33,090
Souvan ou pral kodaj sou yon tablo blan.

29
00:01:33,090 --> 00:01:35,960
Se konsa, yon tablo blan tankou sa a, men souvan sou yon echèl pi piti.

30
00:01:35,960 --> 00:01:38,540
Si w ap gen yon entèvyou nan telefòn, ou pral pwobableman ap lè l sèvi avèk

31
00:01:38,540 --> 00:01:44,030
swa collabedit oswa yon doc Google yo pou yo ka wè ou ap viv kodaj

32
00:01:44,030 --> 00:01:46,500
pandan w ap yo te entèvyou nan telefòn.

33
00:01:46,500 --> 00:01:48,490
Yon entèvyou li menm se tipikman 2 oubyen 3 pwoblèm

34
00:01:48,490 --> 00:01:50,620
tès konesans syans òdinatè ou.

35
00:01:50,620 --> 00:01:54,490
Epi li pral prèske definitivman gen pou wè ak kodaj.

36
00:01:54,490 --> 00:01:59,540
Kalite kesyon ki ke ou pral wè yo anjeneral estrikti done ak algoritm.

37
00:01:59,540 --> 00:02:02,210
Ak nan fè sa yo kalite pwoblèm,

38
00:02:02,210 --> 00:02:07,830
yo pral mande ou, renmen, ki sa ki se tan a ak konpleksite espas, gwo O?

39
00:02:07,830 --> 00:02:09,800
Souvan yo menm tou yo mande pi wo-nivo kesyon,

40
00:02:09,800 --> 00:02:12,530
se konsa, desine yon sistèm,

41
00:02:12,530 --> 00:02:14,770
ki jan ou ta kouche soti kòd ou a?

42
00:02:14,770 --> 00:02:18,370
Ki sa ki interfaces, ki sa ki klas, ki sa ki modil ou gen nan sistèm ou a,

43
00:02:18,370 --> 00:02:20,900
ak ki jan sa yo kominike ansanm?

44
00:02:20,900 --> 00:02:26,130
Se konsa, done estrikti ak algoritm kòm byen ke sistèm desine.

45
00:02:26,130 --> 00:02:29,180
>> Men kèk konsèy jeneral anvan nou plonje nan ka etid nou an.

46
00:02:29,180 --> 00:02:32,300
Mwen panse ke règ ki pi enpòtan an se toujou dwe panse byen fò.

47
00:02:32,300 --> 00:02:36,980
Se entèvyou a sipoze chans ou a montre nan pwosesis panse ou a.

48
00:02:36,980 --> 00:02:39,820
Pwen nan entèvyou a se pou entèvyou a mezire

49
00:02:39,820 --> 00:02:42,660
fason ou panse ak fason ou ale nan yon pwoblèm.

50
00:02:42,660 --> 00:02:45,210
Bagay ki pi mal la ou ka fè se rete an silans pandan tout entèvyou a tout antye.

51
00:02:45,210 --> 00:02:50,090
Se jis pa bon menm.

52
00:02:50,090 --> 00:02:53,230
Lè w ap bay yon kesyon, ou vle asire tou ansòt ou konprann kesyon an.

53
00:02:53,230 --> 00:02:55,350
Se konsa, repete kesyon an tounen nan pwòp mo ou

54
00:02:55,350 --> 00:02:58,920
epi eseye fè travay bon jan yon kèk ka tès senp ki

55
00:02:58,920 --> 00:03:01,530
asire w ke ou konprann kesyon an.

56
00:03:01,530 --> 00:03:05,510
K ap travay nan yon ka tès kèk pral tou ba ou yon entwisyon an sou kòman yo rezoud pwoblèm sa a.

57
00:03:05,510 --> 00:03:11,210
Ou ta ka menm dekouvri yon modèl kèk ede ou rezoud pwoblèm nan.

58
00:03:11,210 --> 00:03:14,500
Pwent gwo yo se pa jwenn fristre.

59
00:03:14,500 --> 00:03:17,060
pa jwenn fwistre.

60
00:03:17,060 --> 00:03:19,060
Entèvyou yo se difisil, men bagay ki pi mal la ou ka fè,

61
00:03:19,060 --> 00:03:23,330
nan adisyon a ke yo te an silans, se yo dwe wè fristre.

62
00:03:23,330 --> 00:03:27,410
Ou pa vle bay enpresyon ke nan yon entèvyou.

63
00:03:27,410 --> 00:03:33,960
Youn nan bagay ki ou - se konsa, anpil moun, lè yo ale nan yon entèvyou,

64
00:03:33,960 --> 00:03:37,150
yo eseye eseye jwenn solisyon a pi bon an premye,

65
00:03:37,150 --> 00:03:39,950
lè reyèlman, gen nan anjeneral yon solisyon furyezman evidan.

66
00:03:39,950 --> 00:03:43,500
Li ta kapab dousman, li ta ka rezèvwa, men ou ta dwe jis deklare li,

67
00:03:43,500 --> 00:03:46,210
jis pou ou gen yon pwen depa nan ki travay pi byen.

68
00:03:46,210 --> 00:03:48,270
Epitou yo, montre yo solisyon an se ralanti, an tèm de

69
00:03:48,270 --> 00:03:52,160
gwo O tan konpleksite oswa konpleksite espas,

70
00:03:52,160 --> 00:03:54,450
yo ap montre entèvyou a ke ou konprann

71
00:03:54,450 --> 00:03:57,510
pwoblèm sa yo lè li ap ekri kòd.

72
00:03:57,510 --> 00:04:01,440
Se konsa, pa bezwen pè vini ak algoritm la ki pi senp premye

73
00:04:01,440 --> 00:04:04,950
ak Lè sa a, travay pi byen apati de la.

74
00:04:04,950 --> 00:04:09,810
Nenpòt kesyon byen lwen tèlman? Oke.

75
00:04:09,810 --> 00:04:11,650
>> Se konsa, nan kite l 'plonje nan pwoblèm premye nou yo.

76
00:04:11,650 --> 00:04:14,790
"Bay yon etalaj de n nonm antye yo, ekri yon fonksyon ki melanz etalaj la

77
00:04:14,790 --> 00:04:20,209
nan plas sa yo ke tout pèrmutasyon nan nonm antye relatif yo n yo se menm chans. "

78
00:04:20,209 --> 00:04:23,470
Ak asime ou gen disponib yon dèlko nonb antye relatif o aza

79
00:04:23,470 --> 00:04:30,980
ki jenere yon nonb antye relatif nan yon seri ki ant 0 a mwen, ranje mwatye.

80
00:04:30,980 --> 00:04:32,970
tout moun konprann kesyon sa a?

81
00:04:32,970 --> 00:04:39,660
M 'ba ou yon etalaj de n nonm antye yo, ak mwen vle fè w chefeul li.

82
00:04:39,660 --> 00:04:46,050
Nan anyè mwen, mwen te ekri yon pwogram kèk yo demontre sa m 'vle di.

83
00:04:46,050 --> 00:04:48,910
Mwen pral chefeul yon etalaj de 20 eleman,

84
00:04:48,910 --> 00:04:52,490
soti nan -10 +9,

85
00:04:52,490 --> 00:04:57,050
e mwen vle ou nan pwodiksyon yon lis tankou sa a.

86
00:04:57,050 --> 00:05:02,890
Se konsa, sa a se opinyon etalaj Ranje mwen an, epi mwen vle fè w chefeul li.

87
00:05:02,890 --> 00:05:07,070
Nou pral fè l 'ankò.

88
00:05:07,070 --> 00:05:13,780
tout moun konprann kesyon an? Oke.

89
00:05:13,780 --> 00:05:16,730
Se konsa, li moute nan ou.

90
00:05:16,730 --> 00:05:21,220
Ki sa ki yo se kèk ide? Èske ou ka fè li kòm n ^ 2, n boutèy demi lit n, n?

91
00:05:21,220 --> 00:05:34,400
Yo admèt sijesyon.

92
00:05:34,400 --> 00:05:37,730
Oke. Se konsa, yon sèl lide, te sijere ke pa Emmy,

93
00:05:37,730 --> 00:05:45,300
se premye kalkile yon nimewo o aza, o aza nonb antye relatif, nan yon seri ki ant 0 a 20.

94
00:05:45,300 --> 00:05:49,840
Se konsa, asime etalaj nou an ki gen yon longè 20.

95
00:05:49,840 --> 00:05:54,800
Nan dyagram nou nan 20 eleman,

96
00:05:54,800 --> 00:05:58,560
sa a se etalaj opinyon nou an.

97
00:05:58,560 --> 00:06:04,590
Epi, koulye a, sijesyon l 'se kreye yon etalaj nouvo,

98
00:06:04,590 --> 00:06:08,440
konsa sa a pral etalaj la randman.

99
00:06:08,440 --> 00:06:12,880
Ak ki baze sou la mwen tounen pa rand -

100
00:06:12,880 --> 00:06:17,580
Se konsa, si mwen te, kite la di, 17,

101
00:06:17,580 --> 00:06:25,640
kopye eleman nan 17th nan pozisyon a an premye.

102
00:06:25,640 --> 00:06:30,300
Koulye a, nou bezwen efase - nou bezwen chanjman tout eleman yo ki isit la

103
00:06:30,300 --> 00:06:36,920
sou sa ke nou gen yon espas nan fen an ak pa gen twou nan mitan yo.

104
00:06:36,920 --> 00:06:39,860
Epi, koulye a nou repete pwosesis la.

105
00:06:39,860 --> 00:06:46,360
Koulye a, nou chwazi yon nouvo nonb antye relatif o aza ant 0 ak 19.

106
00:06:46,360 --> 00:06:52,510
Nou gen yon nouvo mwen isit la, epi nou kopye sa a eleman nan pozisyon sa a.

107
00:06:52,510 --> 00:07:00,960
Lè sa a, nou chanje atik sou yo ak nou repete pwosesis la jiskaske nou gen plen nou an nouvo etalaj.

108
00:07:00,960 --> 00:07:05,890
Ki sa ki se tan an kouri nan sa a algorithm?

109
00:07:05,890 --> 00:07:08,110
Oke, kite la konsidere enpak la nan sa a.

110
00:07:08,110 --> 00:07:10,380
Nou ap déplacement chak eleman.

111
00:07:10,380 --> 00:07:16,800
Lè nou retire sa a mwen, n ap déplacement tout eleman ki nan apre li fin a gòch la.

112
00:07:16,800 --> 00:07:21,600
E ke se yon O (n) pri

113
00:07:21,600 --> 00:07:26,100
paske sa si nou retire eleman nan an premye?

114
00:07:26,100 --> 00:07:29,670
Se konsa, pou chak retire, nou retire -

115
00:07:29,670 --> 00:07:32,170
chak ranvwa supports yon O (n) operasyon,

116
00:07:32,170 --> 00:07:41,520
ak paske nou te fè n ranvwa, sa a mennen nan yon chefeul O (n ^ 2).

117
00:07:41,520 --> 00:07:49,550
Oke. Se konsa, bon kòmanse. Bon kòmanse.

118
00:07:49,550 --> 00:07:55,290
>> Yon lòt sijesyon se yo sèvi ak yon bagay ke yo rekonèt kòm chefeul a knu,

119
00:07:55,290 --> 00:07:57,540
oswa chefeul a Fisher-Yates.

120
00:07:57,540 --> 00:07:59,630
Epitou, se aktyèlman yon chefeul tan lineyè.

121
00:07:59,630 --> 00:08:02,200
Ak lide nan trè sanblab.

122
00:08:02,200 --> 00:08:05,160
Yon fwa ankò, nou genyen etalaj opinyon nou an,

123
00:08:05,160 --> 00:08:08,580
men olye pou yo lè l sèvi avèk de ranje pou D 'nou an / pwodiksyon,

124
00:08:08,580 --> 00:08:13,590
nou itilize pòsyon an premye nan etalaj la nan kenbe tras nan shuffled pòsyon nou an,

125
00:08:13,590 --> 00:08:18,400
epi nou kenbe tras, ak Lè sa a, nou kite rès la nan etalaj nou an pou pòsyon ki unshuffled.

126
00:08:18,400 --> 00:08:24,330
Se konsa, isit la nan sa m 'vle di. Nou kòmanse nan ak - nou chwazi yon mwen,

127
00:08:24,330 --> 00:08:30,910
yon etalaj ki ant 0 a 20.

128
00:08:30,910 --> 00:08:36,150
Konsèy aktyèl nou an, ap lonje dwèt endèks la an premye.

129
00:08:36,150 --> 00:08:39,590
Nou chwazi kèk isit la mwen

130
00:08:39,590 --> 00:08:42,740
e kounye a nou boukante.

131
00:08:42,740 --> 00:08:47,690
Se konsa, si sa a, li te 5 sa a te 4,

132
00:08:47,690 --> 00:08:57,150
etalaj la ki kapab lakòz ap gen 5 isit la ak 4 isit la.

133
00:08:57,150 --> 00:09:00,390
Epi, koulye a nou sonje yon makè isit la.

134
00:09:00,390 --> 00:09:05,770
Tout bagay sa yo bò gòch la ap shuffled,

135
00:09:05,770 --> 00:09:15,160
epi li se tout bagay sa yo dwa pou unshuffled.

136
00:09:15,160 --> 00:09:17,260
Epi, koulye a nou ka repete pwosesis la.

137
00:09:17,260 --> 00:09:25,210
Nou chwazi yon endèks o aza ant 1 ak 20 kounye a.

138
00:09:25,210 --> 00:09:30,650
Se konsa, ta kwè nou nouvo mwen se isit la.

139
00:09:30,650 --> 00:09:39,370
Koulye a, nou boukante sa a mwen ak pozisyon nou an ki ajou nouvo isit la.

140
00:09:39,370 --> 00:09:44,790
Se konsa, nou yon échanjé retounen ak lide tankou sa a.

141
00:09:44,790 --> 00:09:51,630
Kite m 'pote yo moute kòd la fè li pi konkrè.

142
00:09:51,630 --> 00:09:55,290
Nou kòmanse avèk chwa nou an mwen -

143
00:09:55,290 --> 00:09:58,370
nou kòmanse ak mwen egal a 0, nou chwazi yon j kote o aza

144
00:09:58,370 --> 00:10:02,420
nan pòsyon unshuffled nan etalaj la, mwen n 1-.

145
00:10:02,420 --> 00:10:07,280
Se konsa, si mwen isit la, chwazi yon endèks o aza ant isit la ak rès la nan etalaj la,

146
00:10:07,280 --> 00:10:12,410
epi nou boukante.

147
00:10:12,410 --> 00:10:17,550
Sa a se tout kòd la nesesè yo chefeul etalaj ou a.

148
00:10:17,550 --> 00:10:21,670
Nenpòt kesyon?

149
00:10:21,670 --> 00:10:25,530
>> Oke, yon sèl bezwen kesyon ap, poukisa se sa a ki kòrèk?

150
00:10:25,530 --> 00:10:28,360
Poukisa se chak pèmitasyon menm chans?

151
00:10:28,360 --> 00:10:30,410
Apre sa, mwen pa pwal ale travèse prèv sa a,

152
00:10:30,410 --> 00:10:35,970
men anpil pwoblèm nan syans òdinatè ou ka pwouve nan endiksyon.

153
00:10:35,970 --> 00:10:38,520
Konbyen nan ou yo abitye avèk endiksyon?

154
00:10:38,520 --> 00:10:40,590
Oke. Fre.

155
00:10:40,590 --> 00:10:43,610
Se konsa, ou ka pwouve ekzaktitid sa a algorithm pa endiksyon ki senp,

156
00:10:43,610 --> 00:10:49,540
kote ipotèz endiksyon ou ta dwe, asime ke

157
00:10:49,540 --> 00:10:53,290
chefeul mwen retounen chak pèmitasyon menm chans

158
00:10:53,290 --> 00:10:56,120
jiska eleman yo mwen an premye.

159
00:10:56,120 --> 00:10:58,300
Koulye a, konsidere mwen + 1.

160
00:10:58,300 --> 00:11:02,550
Ak nan chemen an, nou chwazi j endèks nou yo boukante,

161
00:11:02,550 --> 00:11:05,230
sa a kondwi a - ak Lè sa a, ou ap travay sou detay yo

162
00:11:05,230 --> 00:11:07,390
omwen yon prèv plen sou rezon ki fè sa a algorithm retounen

163
00:11:07,390 --> 00:11:12,800
chak pèmitasyon ak pwobabilite menm chans.

164
00:11:12,800 --> 00:11:15,940
>> Tout dwa, pwochen pwoblèm.

165
00:11:15,940 --> 00:11:19,170
Se konsa, "yo bay yon seri nonm antye yo, postive, zewo, negatif,

166
00:11:19,170 --> 00:11:21,290
ekri yon fonksyon ki kalkile sòm total la maksimòm

167
00:11:21,290 --> 00:11:24,720
nan nenpòt ki subarray continueous nan etalaj la D '. "

168
00:11:24,720 --> 00:11:28,370
Yon egzanp isit la se, nan ka a kote tout chif yo se pozitif,

169
00:11:28,370 --> 00:11:31,320
Lè sa a, kounye a chwa ki pi bon se pran etalaj nan tout antye.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, egal 10.

171
00:11:34,690 --> 00:11:36,780
Lè ou gen kèk negatif nan la,

172
00:11:36,780 --> 00:11:38,690
nan ka sa a nou jis vle de a an premye

173
00:11:38,690 --> 00:11:44,590
paske chwazi -1 ak / oswa -3 pral pote sòm nou desann.

174
00:11:44,590 --> 00:11:48,120
Pafwa nou ka gen yo kòmanse nan mitan an nan etalaj la.

175
00:11:48,120 --> 00:11:53,500
Pafwa nou ta vle chwazi pa gen anyen nan tout; li pi bon pa pran anyen.

176
00:11:53,500 --> 00:11:56,490
E pafwa li pi bon yo pran otòn lan,

177
00:11:56,490 --> 00:12:07,510
paske bagay la apre li fin se super gwo. Se konsa, nenpòt ide?

178
00:12:07,510 --> 00:12:10,970
(Elèv yo, enkonpreansibl) >> Yeah.

179
00:12:10,970 --> 00:12:13,560
Sipoze mwen pa pran -1.

180
00:12:13,560 --> 00:12:16,170
Lè sa a, swa Mwen chwazi 1,000 ak 20,000,

181
00:12:16,170 --> 00:12:18,630
oswa mwen jis chwazi 3 milya dola nan.

182
00:12:18,630 --> 00:12:20,760
Oke, chwa ki pi bon se pran tout chif yo.

183
00:12:20,760 --> 00:12:24,350
Sa a -1, malgre yo te negatif,

184
00:12:24,350 --> 00:12:31,340
sòm total la antye se pi bon pase yo te Mwen pa pran -1.

185
00:12:31,340 --> 00:12:36,460
Se konsa yonn nan konsèy yo mwen mansyone pi bonè te bay eta evidan an byen klè

186
00:12:36,460 --> 00:12:40,540
ak solisyon an fòs brital premye.

187
00:12:40,540 --> 00:12:44,340
Ki sa ki se solisyon an fòs brital nan pwoblèm sa a? Yeah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Oke, Mwen panse ke solisyon an fòs brital

189
00:12:46,890 --> 00:12:52,600
ta dwe ajoute jiska tout konbinezon ki posib (enkonpreansibl).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Se konsa, lide Jane nan se pran tout posib -

191
00:12:58,250 --> 00:13:01,470
Mwen parafraze - se pran tout posib subarray kontinyèl,

192
00:13:01,470 --> 00:13:07,840
kalkile sòm li yo, ak Lè sa a, pran maksimòm nan tout subarrays yo posib kontinyèl.

193
00:13:07,840 --> 00:13:13,310
Ki sa ki inikman idantifye yon subarray nan etalaj opinyon mwen an?

194
00:13:13,310 --> 00:13:17,380
Tankou, ki sa ki de bagay mwen bezwen? Yeah?

195
00:13:17,380 --> 00:13:19,970
(Elèv yo, enkonpreansibl) >> Dwa.

196
00:13:19,970 --> 00:13:22,130
Yon pi ba mare l 'sou endèks la ak yon anwo endèks mare

197
00:13:22,130 --> 00:13:28,300
inikman detèmine yon subarray kontinyèl.

198
00:13:28,300 --> 00:13:31,400
[Fi elèv] Èske nou estime li a yon etalaj nan nimewo inik?

199
00:13:31,400 --> 00:13:34,280
[Yu] No Se konsa, kesyon li a, èske nou asepte etalaj nou yo -

200
00:13:34,280 --> 00:13:39,000
se etalaj nou tout nimewo inik, e repons la se non.

201
00:13:39,000 --> 00:13:43,390
>> Si nou itilize solisyon brital fòs nou an, Lè sa a, endis yo kòmanse / fen

202
00:13:43,390 --> 00:13:47,200
inikman detèmine subarray kontinyèl nou an.

203
00:13:47,200 --> 00:13:51,680
Se konsa, si nou répétèr pou tout antre kòmansman sa posib,

204
00:13:51,680 --> 00:13:58,320
ak pou tout antre fen> oswa = kòmanse, ak <n,

205
00:13:58,320 --> 00:14:05,570
ou kalkile sòm la, ak Lè sa a, nou pran sòm total la maksimòm nou te wè byen lwen tèlman.

206
00:14:05,570 --> 00:14:07,880
Èske sa se klè?

207
00:14:07,880 --> 00:14:12,230
Ki sa ki O nan gwo sa a solisyon?

208
00:14:12,230 --> 00:14:16,660
Timewise.

209
00:14:16,660 --> 00:14:18,860
Pa byen N ^ 2.

210
00:14:18,860 --> 00:14:25,250
Remake byen ke nou répétèr ki ant 0 a n,

211
00:14:25,250 --> 00:14:27,520
pou ki nan yon sèl pou riban.

212
00:14:27,520 --> 00:14:35,120
Nou répétèr ankò soti nan prèske nan konmansman an nan fen a, yon lòt pou riban.

213
00:14:35,120 --> 00:14:37,640
Epi, koulye a, nan sa, nou dwe rapò kantite moute chak antre,

214
00:14:37,640 --> 00:14:43,810
pou ki nan yon lòt pou riban. Se konsa, nou gen twa pare solèy pou pasan, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Oke. Sa a ale kòm yon pwen depa.

216
00:14:46,560 --> 00:14:53,180
Solisyon nou se pa gen okenn pi mal pase n ^ 3.

217
00:14:53,180 --> 00:14:55,480
tout moun konprann solisyon an fòs brital?

218
00:14:55,480 --> 00:14:59,950
>> Oke. Yon solisyon pi bon an lè l sèvi avèk yon lide rele dinamik pwogramasyon.

219
00:14:59,950 --> 00:15:03,040
Si ou pran CS124, ki se Algoritm ak Done Estrikti,

220
00:15:03,040 --> 00:15:05,680
ou pral vin trè abitye ak teknik sa a.

221
00:15:05,680 --> 00:15:12,190
Ak lide nan ki, eseye bati yon solisyon ak pwoblèm ki pi piti an premye.

222
00:15:12,190 --> 00:15:17,990
Ki sa mwen vle di pa sa a se, nou kounye a gen enkyete sou de bagay: kòmansman ak yon fen.

223
00:15:17,990 --> 00:15:29,340
Epi sa a, anmèdan. E si nou te ka debarase m de youn nan moun ki paramèt?

224
00:15:29,340 --> 00:15:32,650
Youn nan lide se - we're bay pwoblèm orijinal nou an,

225
00:15:32,650 --> 00:15:37,470
jwenn sòm total la maksimòm de nenpòt subarray nan yon seri [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Epi, koulye a nou gen yon subproblem nouvo, kote nou konnen, nan endèks nou an ki ajou mwen,

227
00:15:47,400 --> 00:15:52,520
nou konnen nou dwe konkli la. Subarray nou an dwe fini nan endèks la ye kounye a.

228
00:15:52,520 --> 00:15:57,640
Se konsa, pwoblèm nan rete a se, ki kote nou ta dwe kòmanse subarray nou an?

229
00:15:57,640 --> 00:16:05,160
sa a fè sans? Oke.

230
00:16:05,160 --> 00:16:12,030
Se konsa, mwen te kode sa a leve, epi kite pou yo gade nan ki sa sa a vle di.

231
00:16:12,030 --> 00:16:16,230
Nan codirectory a, gen nan yon pwogram yo rele subarray,

232
00:16:16,230 --> 00:16:19,470
epi li pran nimewo nan atik,

233
00:16:19,470 --> 00:16:25,550
ak li retounen sòm total la subarray maksimòm nan shuffled lis mwen an.

234
00:16:25,550 --> 00:16:29,920
Se konsa, nan ka sa a, subarray maksimòm nou an se 3.

235
00:16:29,920 --> 00:16:34,850
E se te pran pa jis lè l sèvi avèk 2 ak 1.

236
00:16:34,850 --> 00:16:38,050
Se pou nou kouri l 'ankò. Li la tou 3.

237
00:16:38,050 --> 00:16:40,950
Men, tan sa a, sonje ki jan nou te resevwa 3 a.

238
00:16:40,950 --> 00:16:46,690
Nou te pran an - nou jis pran 3 a li menm

239
00:16:46,690 --> 00:16:49,980
paske li nan antoure pa negatif sou tou de bò,

240
00:16:49,980 --> 00:16:55,080
ki pral pote yon sòm <3.

241
00:16:55,080 --> 00:16:57,820
Se pou nou kouri sou 10 atik yo.

242
00:16:57,820 --> 00:17:03,200
Fwa sa a, li nan 7, nou pran 3 nan dirijan ak 4.

243
00:17:03,200 --> 00:17:09,450
Fwa sa a, li nan 8, epi nou jwenn ke lè yo pran 1, 4 ak 3.

244
00:17:09,450 --> 00:17:16,310
Se konsa, nan ba ou yon entwisyon an sou ki jan nou ka rezoud pwoblèm sa a transfòme,

245
00:17:16,310 --> 00:17:18,890
kite a pran yon gade nan sa a subarray.

246
00:17:18,890 --> 00:17:23,460
Nou ap bay sa a etalaj D ', e nou konnen repons lan se 8.

247
00:17:23,460 --> 00:17:26,359
Nou pran 1 an, 4, ak 3.

248
00:17:26,359 --> 00:17:29,090
Men, se pou pou yo gade nan ki jan nou menm te rive ki repons lan.

249
00:17:29,090 --> 00:17:34,160
Se pou yo gade nan subarray a maksimòm ki te fini nan chak nan sa yo endis.

250
00:17:34,160 --> 00:17:40,780
Ki sa ki nan subarray a maksimòm ki gen nan fen nan pozisyon an premye?

251
00:17:40,780 --> 00:17:46,310
[Elèv] Zewo. >> Zewo. Jis pa pran -5 la.

252
00:17:46,310 --> 00:17:50,210
Isit la li pral yo dwe 0 kòm byen. Yeah?

253
00:17:50,210 --> 00:17:56,470
(Elèv yo, enkonpreansibl)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, regrèt, li se yon -3.

255
00:17:58,960 --> 00:18:03,220
Se konsa, sa a se yon 2, sa a se yon -3.

256
00:18:03,220 --> 00:18:08,690
Oke. Se konsa, -4, sa ki nan subarray a maksimòm nan fen ki pozisyon

257
00:18:08,690 --> 00:18:12,910
kote -4 se nan? Zewo.

258
00:18:12,910 --> 00:18:22,570
Youn? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
Koulye a, mwen dwe fini nan kote a kote -2 se nan.

260
00:18:28,060 --> 00:18:39,330
Se konsa, 6, 5, 7, ak yon nan dènye se 4.

261
00:18:39,330 --> 00:18:43,480
Lè konnen ke sa yo, se antre mwen

262
00:18:43,480 --> 00:18:48,130
pou pwoblèm nan transfòme kote mwen dwe fini nan chak nan sa yo endis yo,

263
00:18:48,130 --> 00:18:51,410
Lè sa a, dènye repons mwen se jis, pran yon bale atravè tout,

264
00:18:51,410 --> 00:18:53,580
epi pran kantite maksimòm.

265
00:18:53,580 --> 00:18:55,620
Se konsa, nan ka sa a li nan 8.

266
00:18:55,620 --> 00:19:00,010
Sa implique ke subarray a maksimòm fini nan sa a endèks,

267
00:19:00,010 --> 00:19:04,970
e li te kòmanse yon kote anvan li.

268
00:19:04,970 --> 00:19:09,630
tout moun konprann sa a subarray transfòme?

269
00:19:09,630 --> 00:19:22,160
>> Oke. Oke, kite la konpwan ankò la pou sa a.

270
00:19:22,160 --> 00:19:27,990
Se pou nou konsidere jis premye antre yo kèk.

271
00:19:27,990 --> 00:19:35,930
Se konsa, isit la li te 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Lè sa a, te gen yon -2 isit la, ak ki te fè li desann nan 6.

273
00:19:39,790 --> 00:19:50,800
Se konsa, si mwen rele antre a nan pozisyon mwen subproblem (mwen),

274
00:19:50,800 --> 00:19:54,910
kouman mwen ka itilize repons lan nan yon subproblem anvan

275
00:19:54,910 --> 00:19:59,360
reponn sa a subproblem?

276
00:19:59,360 --> 00:20:04,550
Si m 'gade nan, kite la di, sa a antre.

277
00:20:04,550 --> 00:20:09,190
Kouman mwen ka kalkile repons lan 6 pa gade

278
00:20:09,190 --> 00:20:18,780
yon konbinezon de sa a etalaj ak repons yo nan subproblems anvan nan sa a etalaj? Wi?

279
00:20:18,780 --> 00:20:22,800
[Fi elèv] Ou pran etalaj la nan sòm total

280
00:20:22,800 --> 00:20:25,430
nan yon pozisyon nan dwa anvan li, se konsa 8 la,

281
00:20:25,430 --> 00:20:32,170
ak Lè sa a, ou ajoute subproblem aktyèl la.

282
00:20:32,170 --> 00:20:36,460
[Yu] Se konsa, sijesyon li se fè yon gade nan de nimewo sa yo,

283
00:20:36,460 --> 00:20:40,090
nimewo sa a ak nimewo sa a.

284
00:20:40,090 --> 00:20:50,130
Se konsa, sa a 8 refere a repons lan pou subproblem a (mwen - 1).

285
00:20:50,130 --> 00:20:57,300
Li kite yo rele A. D 'etalaj mwen

286
00:20:57,300 --> 00:21:01,470
Yo nan lòd yo jwenn yon subarray maksimòm ki fini nan pozisyon mwen,

287
00:21:01,470 --> 00:21:03,980
Mwen gen de chwa: Mwen ka swa kontinye subarray la

288
00:21:03,980 --> 00:21:09,790
ki te fini nan endèks la anvan, oswa kòmanse yon etalaj nouvo.

289
00:21:09,790 --> 00:21:14,190
Si m 'te kontinye subarray a ki te kòmanse nan endèks la anvan,

290
00:21:14,190 --> 00:21:19,260
Lè sa a, sòm total la maksimòm mwen kapab reyalize se repons lan nan subproblem a anvan

291
00:21:19,260 --> 00:21:24,120
plis antre nan etalaj aktyèl.

292
00:21:24,120 --> 00:21:27,550
Men, mwen menm tou nou gen chwa pou yo kòmanse yon subarray nouvo,

293
00:21:27,550 --> 00:21:30,830
nan ka sa a sòm total la se 0.

294
00:21:30,830 --> 00:21:42,860
Se konsa, repons lan se max nan 0, subproblem mwen - 1, plis antre nan etalaj aktyèl.

295
00:21:42,860 --> 00:21:46,150
sa a ankò fè sans?

296
00:21:46,150 --> 00:21:50,840
Ankò nou an, jan nou jis dekouvri, se subproblem mwen

297
00:21:50,840 --> 00:21:54,740
ki egal a maksimòm la nan subproblem a anvan plis antre aktyèl etalaj m 'yo,

298
00:21:54,740 --> 00:22:01,490
ki vle di kontinye subarray anvan an,

299
00:22:01,490 --> 00:22:07,250
oswa 0, kòmanse yon nouvo subarray nan endèks mwen ye kounye a.

300
00:22:07,250 --> 00:22:10,060
E yon fwa nou te bati moute tablo sa a nan solisyon, Lè sa a, dènye repons nou an,

301
00:22:10,060 --> 00:22:13,950
jis fè yon bale lineyè atravè etalaj la subproblem

302
00:22:13,950 --> 00:22:19,890
epi pran kantite maksimòm.

303
00:22:19,890 --> 00:22:23,330
Sa a se yon aplikasyon egzak nan sa mwen jis te di.

304
00:22:23,330 --> 00:22:27,320
Se konsa, nou kreye yon etalaj subproblem nouvo, subproblems.

305
00:22:27,320 --> 00:22:32,330
Antre an premye se swa 0 oswa antre a an premye, maksimòm tout moun sa yo de.

306
00:22:32,330 --> 00:22:35,670
Ak pou tout rès subproblems yo

307
00:22:35,670 --> 00:22:39,810
nou itilize ankò an egzak nou jis dekouvri.

308
00:22:39,810 --> 00:22:49,960
Koulye a, nou kalkile maksimòm la nan etalaj subproblems nou an, epi ki nan dènye repons nou yo.

309
00:22:49,960 --> 00:22:54,130
>> Se konsa, kouman kantite espas yo nou lè l sèvi avèk sa a nan algorithm?

310
00:22:54,130 --> 00:23:01,470
Si ou te sèlman pran CS50, lè sa a ou pa ta ka mwen te diskite espas anpil.

311
00:23:01,470 --> 00:23:07,750
Oke, yon sèl bagay a nòt la ki mwen te rele malok isit la ak n gwosè.

312
00:23:07,750 --> 00:23:13,590
Ki sa ki ki te sijere nou sou sa?

313
00:23:13,590 --> 00:23:17,450
Sa a algorithm itilize espas lineyè.

314
00:23:17,450 --> 00:23:21,030
Nou ka fè pi byen?

315
00:23:21,030 --> 00:23:30,780
Eske gen yon bagay ke ou avi ke se nesesè kalkile repons final la?

316
00:23:30,780 --> 00:23:33,290
Mwen devine yon kesyon pi bon se, ki sa ki enfòmasyon

317
00:23:33,290 --> 00:23:40,680
nou pa bezwen pote tout wout la a la fen?

318
00:23:40,680 --> 00:23:44,280
Koulye a, si nou gade nan de liy sa yo,

319
00:23:44,280 --> 00:23:47,720
nou sèlman pran swen sou subproblem anvan an,

320
00:23:47,720 --> 00:23:50,910
epi nou sèlman pran swen sou maksimòm an nou te janm wè byen lwen tèlman.

321
00:23:50,910 --> 00:23:53,610
Kalkile repons final nou an, nou pa bezwen etalaj a tout antye.

322
00:23:53,610 --> 00:23:57,450
Nou bezwen sèlman nimewo nan dènye, dènye de nonb.

323
00:23:57,450 --> 00:24:02,630
Denye nimewo pou etalaj la subproblem, ak nimewo dènye pou maksimòm la.

324
00:24:02,630 --> 00:24:07,380
Se konsa, an reyalite, nou ka Fuse sa yo pasan ansanm

325
00:24:07,380 --> 00:24:10,460
epi ale nan lineyè espas nan espas konstan.

326
00:24:10,460 --> 00:24:15,830
Kouran sòm twò lwen, isit la, ranplase wòl nan subproblem, etalaj subproblem nou an.

327
00:24:15,830 --> 00:24:20,020
Sòm Se konsa, kounye a, twò lwen, se repons lan nan subproblem a anvan yo.

328
00:24:20,020 --> 00:24:23,450
E ke sòm, se konsa, lwen, pran plas nan max nou an.

329
00:24:23,450 --> 00:24:28,100
Nou kalkile maksimòm a jan nou ale ansanm.

330
00:24:28,100 --> 00:24:30,890
Se konsa, nou ale nan espas lineyè nan espas konstan,

331
00:24:30,890 --> 00:24:36,650
ak nou menm tou nou gen yon solisyon lineyè nan pwoblèm subarray nou an.

332
00:24:36,650 --> 00:24:40,740
>> Sa yo kalite kesyon ki ou pral jwenn pandan yon entèvyou.

333
00:24:40,740 --> 00:24:44,450
Ki sa ki konpleksite nan tan; sa ki konpleksite nan espas?

334
00:24:44,450 --> 00:24:50,600
Èske ou ka fè pi byen? Èske gen bagay ki nesesè kenbe nan jiwon l?

335
00:24:50,600 --> 00:24:55,270
Mwen te fè sa a mete aksan sou analyses ki ou ta dwe pran sou pwòp ou a

336
00:24:55,270 --> 00:24:57,400
kòm w ap travay nan pwoblèm sa yo.

337
00:24:57,400 --> 00:25:01,710
Toujou dwe mande tèt ou, "Èske mwen ka fè pi byen?"

338
00:25:01,710 --> 00:25:07,800
An reyalite, nou ka fè pi bon pase sa a?

339
00:25:07,800 --> 00:25:10,730
Triye nan yon kesyon Trick. Ou pa kapab, paske ou bezwen

340
00:25:10,730 --> 00:25:13,590
omwen li D 'a pwoblèm nan.

341
00:25:13,590 --> 00:25:15,570
Se konsa, reyalite a ke ou bezwen omwen li D 'a nan pwoblèm nan

342
00:25:15,570 --> 00:25:19,580
vle di ke ou pa kapab fè pi bon pase tan lineyè,

343
00:25:19,580 --> 00:25:22,870
ak ou pa kapab fè pi bon pase espas konstan.

344
00:25:22,870 --> 00:25:27,060
Se konsa, sa a se, an reyalite, solisyon an pi byen pwoblèm sa a.

345
00:25:27,060 --> 00:25:33,040
Kesyon? Oke.

346
00:25:33,040 --> 00:25:35,190
>> Stock mache pwoblèm:

347
00:25:35,190 --> 00:25:38,350
"Bay yon etalaj de n nonm antye yo, pozitif, zewo, oswa negatif,

348
00:25:38,350 --> 00:25:41,680
ki reprezante pri a nan yon estòk sou n jou,

349
00:25:41,680 --> 00:25:44,080
ekri yon fonksyon kalkile pwofi a maksimòm ou ka fè

350
00:25:44,080 --> 00:25:49,350
bay sa ou achte ak vann egzakteman 1 stock nan jou sa yo n. "

351
00:25:49,350 --> 00:25:51,690
Esansyèlman, nou vle achte ki ba, vann segondè.

352
00:25:51,690 --> 00:25:58,580
E nou vle konnen ki Peye a pi bon nou ka fè.

353
00:25:58,580 --> 00:26:11,500
Ale tounen nan pwent m 'yo, sa ki se imedyatman klè, repons lan ki pi senp, men li la dousman?

354
00:26:11,500 --> 00:26:17,690
Wi? (Elèv yo, enkonpreansibl) >> Wi.

355
00:26:17,690 --> 00:26:21,470
>> Se konsa, ou ta jis ale menm si ak gade nan pri yo stock

356
00:26:21,470 --> 00:26:30,550
nan chak pwen nan tan, (enkonpreansibl).

357
00:26:30,550 --> 00:26:33,990
[Yu] Oke, kidonk solisyon li - sijesyon li nan informatique

358
00:26:33,990 --> 00:26:37,380
pi ba a ak kalkile pi wo a pa nesesèman travay

359
00:26:37,380 --> 00:26:42,470
paske pi wo a kapab rive anvan ki pi ba a.

360
00:26:42,470 --> 00:26:47,340
Se konsa, sa se solisyon an fòs brital sa a pwoblèm?

361
00:26:47,340 --> 00:26:53,150
Ki sa ki yo se bagay ki de ke mwen bezwen inikman detèmine pwofi a mwen fè? Dwat.

362
00:26:53,150 --> 00:26:59,410
Solisyon an fòs brital se - oh, se konsa, sijesyon George a se nou bezwen wè sèlman de jou

363
00:26:59,410 --> 00:27:02,880
inikman detèmine pwofi a nan de jou sa yo.

364
00:27:02,880 --> 00:27:06,660
Se konsa, nou kalkile chak pè, renmen achte / vann,

365
00:27:06,660 --> 00:27:12,850
kalkile pwofi a, ki ta ka negatif oswa pozitif oswa zewo.

366
00:27:12,850 --> 00:27:18,000
Kalkile pwofi a maksimòm ke nou fè apwè yo fin iteration sou tout pè jou.

367
00:27:18,000 --> 00:27:20,330
Ki pral dènye repons nou yo.

368
00:27:20,330 --> 00:27:25,730
E ke solisyon yo pral O (n ^ 2), paske gen n chwazi de pè -

369
00:27:25,730 --> 00:27:30,270
nan jou ke ou ka chwazi nan mitan jou fen.

370
00:27:30,270 --> 00:27:32,580
Oke, kidonk mwen pa pwal ale sou solisyon an fòs brital isit la.

371
00:27:32,580 --> 00:27:37,420
Mwen pral di ou ke gen nan yon boutèy demi lit n n solisyon an.

372
00:27:37,420 --> 00:27:45,550
Ki sa ki algorithm ou kounye a konnen se n boutèy demi lit n?

373
00:27:45,550 --> 00:27:50,730
Li pa yon kesyon Trick.

374
00:27:50,730 --> 00:27:54,790
>> Rantre zèl. Rantre sòt se n boutèy demi lit n,

375
00:27:54,790 --> 00:27:57,760
ak an reyalite, yon fason pou rezoud pwoblèm sa a se sèvi ak

376
00:27:57,760 --> 00:28:04,400
yon kalite sòt unifye nan lide rele, an jeneral, separe ak konkeri.

377
00:28:04,400 --> 00:28:07,570
Ak lide a se jan sa a.

378
00:28:07,570 --> 00:28:12,400
Ou vle kalkile achte a pi byen / vann pè nan mwatye gòch la.

379
00:28:12,400 --> 00:28:16,480
Jwenn Peye nan pi bon ou ka fè, jis ak n nan premye sou de jou.

380
00:28:16,480 --> 00:28:19,780
Lè sa a, ou vle oompute achte a pi byen / vann pè sou mwatye a dwat,

381
00:28:19,780 --> 00:28:23,930
se konsa n an dènye sou de jou.

382
00:28:23,930 --> 00:28:32,400
Epi, koulye a kesyon an se, ki jan nou rantre sa yo solisyon tounen ansanm?

383
00:28:32,400 --> 00:28:36,320
Wi? (Elèv yo, enkonpreansibl)

384
00:28:36,320 --> 00:28:49,890
>> Okay. Se konsa, kite m 'desine yon foto.

385
00:28:49,890 --> 00:29:03,870
Wi? (George, enkonpreansibl)

386
00:29:03,870 --> 00:29:06,450
>> Egzakteman. Solisyon George a se egzakteman dwa.

387
00:29:06,450 --> 00:29:10,040
Se konsa, sijesyon li ye, se premye kalkile pi byen achte / vann pè a,

388
00:29:10,040 --> 00:29:16,050
ak ki fèt nan mwatye a gòch, kidonk kite a rele ki bò gòch, yo kite.

389
00:29:16,050 --> 00:29:20,790
Pi bon achte / vann pè ki fèt nan mwatye a dwat.

390
00:29:20,790 --> 00:29:25,180
Men, si nou sèlman konpare nimewo sa yo de, nou ap manke ka a

391
00:29:25,180 --> 00:29:30,460
kote nou achte isit la ak vann yon kote nan mwatye a dwat.

392
00:29:30,460 --> 00:29:33,810
Nou achte nan mwatye gòch la, vann nan mwatye a dwat.

393
00:29:33,810 --> 00:29:38,490
Ak pi bon fason yo kalkile pi byen achte / vann pè a ki porte tou de mwatye

394
00:29:38,490 --> 00:29:43,480
se kalkile minimòm la isit la ak kalkile maksimòm an isit la

395
00:29:43,480 --> 00:29:45,580
epi pran diferans yo.

396
00:29:45,580 --> 00:29:50,850
Se konsa, de ka yo kote pè a achte / vann fèt sèlman isit la,

397
00:29:50,850 --> 00:30:01,910
sèlman isit la, oswa sou tou de mwatye yo defini pa twa nimewo sa yo.

398
00:30:01,910 --> 00:30:06,450
Se konsa, algorithm nou yo rantre solisyon nou an tounen ansanm,

399
00:30:06,450 --> 00:30:08,350
nou vle kalkile pi byen achte / vann pè a

400
00:30:08,350 --> 00:30:13,120
kote nou achte sou mwatye nan bò gòch ak vann sou mwatye a dwat.

401
00:30:13,120 --> 00:30:16,740
Ak pi bon fason yo fè sa se kalkile pri ki pi ba a nan mwatye a an premye,

402
00:30:16,740 --> 00:30:20,360
pri ki pi wo nan mwatye nan dwa, epi pran diferans yo.

403
00:30:20,360 --> 00:30:25,390
Rézilta twa pwofi yo, chif sa yo twa, ou pran maksimòm a nan twa a,

404
00:30:25,390 --> 00:30:32,720
ak sa a, se pwofi nan pi bon ou ka fè sou jou sa yo premye ak yon fen.

405
00:30:32,720 --> 00:30:36,940
Isit la liy ki enpòtan yo se nan wouj.

406
00:30:36,940 --> 00:30:41,160
Sa a se yon apèl repetitif kalkile repons lan nan mwatye a gòch.

407
00:30:41,160 --> 00:30:44,760
Sa a se yon apèl repetitif kalkile repons lan nan mwatye a dwat.

408
00:30:44,760 --> 00:30:50,720
Sa yo de pou pasan kalkile min a ak max la sou mwatye nan kite la ak dwa, respektivman.

409
00:30:50,720 --> 00:30:54,970
Koulye a, mwen kalkile pwofi a ki porte tou de mwatye,

410
00:30:54,970 --> 00:31:00,530
ak repons lan final la maksimòm la nan sa yo twa.

411
00:31:00,530 --> 00:31:04,120
Oke.

412
00:31:04,120 --> 00:31:06,420
>> Se konsa, asire w, nou gen yon algorithm, men kesyon an pi gwo se,

413
00:31:06,420 --> 00:31:08,290
ki sa ki konpleksite nan tan sa a?

414
00:31:08,290 --> 00:31:16,190
Ak rezon an poukisa mwen mansyone unifye sòt se ke fòm sa a nan divize repons lan

415
00:31:16,190 --> 00:31:19,200
an de ak Lè sa a, Fusion solisyon nou an tounen ansanm

416
00:31:19,200 --> 00:31:23,580
se egzakteman fòm lan nan sòt unifye.

417
00:31:23,580 --> 00:31:33,360
Se konsa, kite m 'ale nan dire a.

418
00:31:33,360 --> 00:31:41,340
Si nou defini yon t fonksyon (n) yo dwe nimewo a nan etap

419
00:31:41,340 --> 00:31:50,010
pou jou n,

420
00:31:50,010 --> 00:31:54,350
apèl de nou repetitif

421
00:31:54,350 --> 00:32:00,460
yo chak pral koute t (n / 2),

422
00:32:00,460 --> 00:32:03,540
ak gen nan de nan sa yo apèl.

423
00:32:03,540 --> 00:32:10,020
Koulye a, mwen bezwen kalkile minimòm lan nan mwatye a gòch,

424
00:32:10,020 --> 00:32:17,050
ki mwen ka fè nan n / tan 2, plis maksimòm a nan mwatye a dwat.

425
00:32:17,050 --> 00:32:20,820
Se konsa, sa a se jis n.

426
00:32:20,820 --> 00:32:25,050
Lè sa a, plis kèk travay konstan.

427
00:32:25,050 --> 00:32:27,770
Lè sa a ankò ekwasyon

428
00:32:27,770 --> 00:32:35,560
se egzakteman ekwasyon an ankò pou sòt unifye.

429
00:32:35,560 --> 00:32:39,170
Ak nou tout konnen ke unifye sòt se n boutèy demi lit n tan.

430
00:32:39,170 --> 00:32:46,880
Se poutèt sa, se algorithm nou an tou n boutèy demi lit n tan.

431
00:32:46,880 --> 00:32:52,220
sa a iterasyon fè sans?

432
00:32:52,220 --> 00:32:55,780
Jis yon rapèl tou kout sou sa a:

433
00:32:55,780 --> 00:32:59,170
T (n) se nimewo a nan etap sa yo kalkile pwofi a maksimòm

434
00:32:59,170 --> 00:33:02,750
sou kou nan n jou.

435
00:33:02,750 --> 00:33:06,010
Wout la nou fann moute apèl repetitif nou

436
00:33:06,010 --> 00:33:11,980
se lè w rele solisyon nou an sou premye jou yo n / 2,

437
00:33:11,980 --> 00:33:14,490
pou ki nan yon sèl rele,

438
00:33:14,490 --> 00:33:16,940
ak Lè sa a, nou rele ankò sou dezyèm mwatye a.

439
00:33:16,940 --> 00:33:20,440
Se konsa, sa a, se de apèl.

440
00:33:20,440 --> 00:33:25,310
Lè sa a, nou jwenn yon minimòm sou mwatye nan bò gòch, ki nou ka fè nan tan lineyè,

441
00:33:25,310 --> 00:33:29,010
jwenn maksimòm a nan mwatye nan dwa, ki nou ka fè nan tan lineyè.

442
00:33:29,010 --> 00:33:31,570
Se konsa, n / 2 + n / 2 se jis n.

443
00:33:31,570 --> 00:33:36,020
Lè sa a, nou gen kèk travay konstan, ki se tankou fè aritmetik.

444
00:33:36,020 --> 00:33:39,860
Ekwasyon sa a ankò se egzakteman ekwasyon an ankò pou sòt unifye.

445
00:33:39,860 --> 00:33:55,490
Pakonsekan, algorithm chefeul nou an se tou n ale n.

446
00:33:55,490 --> 00:33:58,520
Se konsa, kouman kantite espas yo nou lè l sèvi avèk?

447
00:33:58,520 --> 00:34:04,910
Se pou nou tounen nan kòd la.

448
00:34:04,910 --> 00:34:09,420
>> Yon kesyon pi bon se, konbyen ankadreman chemine nou janm genyen nan nenpòt moman?

449
00:34:09,420 --> 00:34:11,449
Depi nou ap sèvi ak rkursyon,

450
00:34:11,449 --> 00:34:23,530
ki kantite ankadreman chemine detèmine itilizasyon espas nou yo.

451
00:34:23,530 --> 00:34:29,440
Se pou nou konsidere n = 8.

452
00:34:29,440 --> 00:34:36,889
Nou rele chefeul sou 8,

453
00:34:36,889 --> 00:34:41,580
ki pral rele chefeul sou kat antre yo an premye,

454
00:34:41,580 --> 00:34:46,250
ki pral rele yon chefeul sou de antre yo an premye.

455
00:34:46,250 --> 00:34:51,550
Se konsa, chemine nou an, se - sa a se pil nou an.

456
00:34:51,550 --> 00:34:54,980
Lè sa a, nou rele chefeul ankò sou 1,

457
00:34:54,980 --> 00:34:58,070
ak se sa ki ka baz nou an se, konsa nou retounen imedyatman.

458
00:34:58,070 --> 00:35:04,700
Èske nou janm gen plis pase sa a ankadreman chemine anpil?

459
00:35:04,700 --> 00:35:08,880
No Paske chak fwa nou fè yon invoké,

460
00:35:08,880 --> 00:35:10,770
yon invoké repetitif chefeul,

461
00:35:10,770 --> 00:35:13,950
nou divize gwosè nou yo nan mwatye.

462
00:35:13,950 --> 00:35:17,020
Se konsa, la pou maksimòm kantite ankadreman chemine nou janm genyen nan nenpòt moman

463
00:35:17,020 --> 00:35:28,460
se sou lòd la nan boutèy n chemine ankadreman.

464
00:35:28,460 --> 00:35:42,460
Chak ankadreman chemine ki gen yon plas konstan,

465
00:35:42,460 --> 00:35:44,410
ak Se poutèt sa kantite total espas,

466
00:35:44,410 --> 00:35:49,240
kantite lajan maksimòm nan espas nou janm sèvi ak se O (boutèy demi lit n) espas

467
00:35:49,240 --> 00:36:03,040
kote n se kantite jou.

468
00:36:03,040 --> 00:36:07,230
>> Koulye a, toujou mande tèt ou, "Èske nou ka fè pi byen?"

469
00:36:07,230 --> 00:36:12,390
Ak nan patikilye, nou ka diminye sa a nan yon pwoblèm nou te deja rezoud?

470
00:36:12,390 --> 00:36:20,040
Yon allusion: nou sèlman diskite de pwoblèm lòt anvan sa a, e li pa k ap pase yo dwe chefeul.

471
00:36:20,040 --> 00:36:26,200
Nou ka konvèti pwoblèm sa a mache dechanj nan pwoblèm nan subarray maksimòm.

472
00:36:26,200 --> 00:36:40,100
Ki jan nou ka fè sa?

473
00:36:40,100 --> 00:36:42,570
Youn nan ou? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, enkonpreansibl)

475
00:36:47,680 --> 00:36:53,860
[Yu] Egzakteman.

476
00:36:53,860 --> 00:36:59,940
Se konsa, pwoblèm nan subarray maksimòm,

477
00:36:59,940 --> 00:37:10,610
nou ap chèche pou yon sòm sou yon subarray kontinyèl.

478
00:37:10,610 --> 00:37:16,230
Ak sijesyon Emmy a pou pwoblèm nan aksyon,

479
00:37:16,230 --> 00:37:30,720
konsidere chanjman yo, oswa dèlta yo.

480
00:37:30,720 --> 00:37:37,440
Ak yon foto nan sa a se - sa a se pri a nan yon estòk,

481
00:37:37,440 --> 00:37:42,610
Men, si nou te pran diferans ki genyen ant chak jou youn apre lòt -

482
00:37:42,610 --> 00:37:45,200
se konsa nou wè ke pri a maksimòm, maksimòm pwofi nou te ka fè

483
00:37:45,200 --> 00:37:50,070
se si nou achte isit la ak vann isit la.

484
00:37:50,070 --> 00:37:54,240
Men, se pou pou yo gade nan kontinyèl la - kite pou yo gade nan pwoblèm nan subarray.

485
00:37:54,240 --> 00:38:02,510
Se konsa, isit la, nou ka fè - pral soti isit la isit la,

486
00:38:02,510 --> 00:38:08,410
nou gen yon chanjman pozitif, ak Lè sa a, pral soti nan isit la yo isit la nou gen yon chanjman negatif.

487
00:38:08,410 --> 00:38:14,220
Men, lè sa a, pral soti nan isit la yo isit la nou gen yon gwo chanjman pozitif.

488
00:38:14,220 --> 00:38:20,930
Ak sa yo, se chanjman sa yo ke nou vle rapò kantite jiska jwenn pwofi final nou an.

489
00:38:20,930 --> 00:38:25,160
Lè sa a, nou gen plis negatif chanjman isit la.

490
00:38:25,160 --> 00:38:29,990
Kle a ou diminye nan kantite pwoblèm stock nou an, nan pwoblèm maksimòm subarray nou

491
00:38:29,990 --> 00:38:36,630
se konsidere delta ki genyen ant jou.

492
00:38:36,630 --> 00:38:40,630
Se konsa, nou kreye yon etalaj nouvo rele dèlta,

493
00:38:40,630 --> 00:38:43,000
inisyalize antre nan premye yo dwe 0,

494
00:38:43,000 --> 00:38:46,380
ak Lè sa a, pou chak dèlta (mwen), kite sa dwe diferans lan

495
00:38:46,380 --> 00:38:52,830
nan etalaj opinyon mwen an (mwen), ak etalaj (mwen - 1).

496
00:38:52,830 --> 00:38:55,530
Lè sa a, nou rele pwosedi woutin nou an pou yon maksimòm subarray

497
00:38:55,530 --> 00:39:01,500
pase nan etalaj yon Delta la.

498
00:39:01,500 --> 00:39:06,440
Epi paske subarray maksimòm a se tan lineyè,

499
00:39:06,440 --> 00:39:09,370
ak sa a rediksyon, pwosesis sa a pou kreye sa a etalaj delta,

500
00:39:09,370 --> 00:39:11,780
se tou tan lineyè,

501
00:39:11,780 --> 00:39:19,060
Lè sa a, solisyon an final pou aksyon se O (n) travay plis O (n) travay, se toujou O (n) travay.

502
00:39:19,060 --> 00:39:23,900
Se konsa, nou gen yon solisyon tan lineyè nan pwoblèm nou yo.

503
00:39:23,900 --> 00:39:29,610
tout moun konprann sa a transfòmasyon?

504
00:39:29,610 --> 00:39:32,140
>> An jeneral, yon bon lide ke ou ta dwe toujou gen

505
00:39:32,140 --> 00:39:34,290
se eseye diminye yon pwoblèm nouvo ki w ap wè.

506
00:39:34,290 --> 00:39:37,700
Si li sanble abitye nan yon pwoblèm fin vye granmoun,

507
00:39:37,700 --> 00:39:39,590
eseye diminye li nan yon pwoblèm fin vye granmoun.

508
00:39:39,590 --> 00:39:41,950
Men, si ou ka sèvi ak tout zouti sa yo ke ou te itilize sou pwoblèm nan fin vye granmoun

509
00:39:41,950 --> 00:39:46,450
rezoud pwoblèm nan nouvo.

510
00:39:46,450 --> 00:39:49,010
Se konsa, vlope moute, entèvyou teknik ki difisil.

511
00:39:49,010 --> 00:39:52,280
Pwoblèm sa yo yo se pwobableman kèk nan pwoblèm ki pi difisil

512
00:39:52,280 --> 00:39:54,700
ke ou ta ka wè nan yon entèvyou,

513
00:39:54,700 --> 00:39:57,690
Se konsa, si ou pa konprann tout pwoblèm sa yo ke mwen jis kouvri, li nan oke.

514
00:39:57,690 --> 00:40:01,080
Sa yo se kèk nan pwoblèm yo plis enteresan.

515
00:40:01,080 --> 00:40:03,050
Pratike, pratike, pratike.

516
00:40:03,050 --> 00:40:08,170
Mwen te bay yon anpil nan pwoblèm nan feyè a, se konsa definitivman tcheke sa yo deyò.

517
00:40:08,170 --> 00:40:11,690
Ak bon chans sou entèvyou ou an. Tout resous m 'yo ap afiche nan lyen sa a,

518
00:40:11,690 --> 00:40:15,220
ak youn nan zanmi ansyen mwen te ofri fè Metye entèvyou teknik,

519
00:40:15,220 --> 00:40:22,050
Se konsa, si w ap enterese, imel Will Yao nan ki adrès imel.

520
00:40:22,050 --> 00:40:26,070
Si ou gen kèk kesyon, ou kapab mande m '.

521
00:40:26,070 --> 00:40:28,780
ou nèg gen kesyon espesifik ki gen rapò ak entèvyou teknik

522
00:40:28,780 --> 00:40:38,440
oswa nenpòt ki pwoblèm nou te wè byen lwen tèlman?

523
00:40:38,440 --> 00:40:49,910
Oke. Oke, bon chans sou entèvyou ou an.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]