1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Семинар на тема: Технически Интервюта]

2
00:00:02,640 --> 00:00:04,630
[Кени Ю, Харвардския университет]

3
00:00:04,630 --> 00:00:08,910
[Това е CS50. [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Здравейте всички, аз съм Кени. В момента съм младши учи компютърни науки.

5
00:00:12,420 --> 00:00:17,310
Аз съм бивш CS TF, и Бих искал да имам това, когато бях на underclassman,

6
00:00:17,310 --> 00:00:19,380
и затова давам този семинар.

7
00:00:19,380 --> 00:00:21,370
Така че се надявам да ви хареса.

8
00:00:21,370 --> 00:00:23,470
Този семинар е за техническите интервюта,

9
00:00:23,470 --> 00:00:26,650
и всичките ми ресурси могат да бъдат намерени в тази връзка,

10
00:00:26,650 --> 00:00:32,350
тази връзка тук, няколко на ресурсите.

11
00:00:32,350 --> 00:00:36,550
Така че направих списък с проблеми, всъщност, доста проблеми.

12
00:00:36,550 --> 00:00:40,800
Също така общо страница ресурси там, където можем да намерим съвети

13
00:00:40,800 --> 00:00:42,870
за това как да се подготвят за интервю,

14
00:00:42,870 --> 00:00:46,470
съвети за това какво трябва да правите по време на реалното интервю,

15
00:00:46,470 --> 00:00:51,910
, както и как да подходим към проблемите и ресурси за бъдещи справки.

16
00:00:51,910 --> 00:00:53,980
Това е онлайн.

17
00:00:53,980 --> 00:00:58,290
И само да предговор този семинар, за отказ от отговорност,

18
00:00:58,290 --> 00:01:00,690
като това не трябва - подготовката на интервю

19
00:01:00,690 --> 00:01:02,800
не трябва да се ограничава в този списък.

20
00:01:02,800 --> 00:01:04,750
Това има за цел единствено да бъде водач,

21
00:01:04,750 --> 00:01:08,890
и определено трябва да вземат всичко, което казвам със зърно на сол,

22
00:01:08,890 --> 00:01:14,620
но също така да използвате всичко, което да ви помогне в подготовката на интервю.

23
00:01:14,620 --> 00:01:16,400
>> Отивам да се ускори през следващите няколко слайда

24
00:01:16,400 --> 00:01:18,650
така че можем да стигнем до реални казуси.

25
00:01:18,650 --> 00:01:23,630
Структурата на интервю за софтуерно инженерство postion,

26
00:01:23,630 --> 00:01:26,320
обикновено е 30 до 45 минути,

27
00:01:26,320 --> 00:01:29,810
няколко кръга, в зависимост от компанията.

28
00:01:29,810 --> 00:01:33,090
Често ще се кодиране на бяла дъска.

29
00:01:33,090 --> 00:01:35,960
Така бяла дъска така, но често и в по-малък мащаб.

30
00:01:35,960 --> 00:01:38,540
Ако имате интервю по телефона, най-вероятно ще се използва

31
00:01:38,540 --> 00:01:44,030
collabedit или Google Doc така че те могат да се видим на живо кодиране

32
00:01:44,030 --> 00:01:46,500
докато сте интервюирани по телефона.

33
00:01:46,500 --> 00:01:48,490
Самото интервю обикновено е два или три проблема

34
00:01:48,490 --> 00:01:50,620
тестване на познанията си в областта на компютърните науки.

35
00:01:50,620 --> 00:01:54,490
И това почти със сигурност ще включва кодиране.

36
00:01:54,490 --> 00:01:59,540
Видове въпроси, които ще видите обикновено са структури от данни и алгоритми.

37
00:01:59,540 --> 00:02:02,210
И в правенето на тези видове проблеми,

38
00:02:02,210 --> 00:02:07,830
те ще ви попитам, харесвате, какво е времето и сложността пространство, Big O?

39
00:02:07,830 --> 00:02:09,800
Често те също задават въпроси от по-високо ниво,

40
00:02:09,800 --> 00:02:12,530
така, проектирането на системата,

41
00:02:12,530 --> 00:02:14,770
как ще изложи кода си?

42
00:02:14,770 --> 00:02:18,370
Какво интерфейси, какви класове, какви модули да имате във вашата система,

43
00:02:18,370 --> 00:02:20,900
и как те си взаимодействат заедно?

44
00:02:20,900 --> 00:02:26,130
Така структури от данни и алгоритми, както и проектиране на системи.

45
00:02:26,130 --> 00:02:29,180
>> Някои общи съвети, преди да се потопите в нашите казуси.

46
00:02:29,180 --> 00:02:32,300
Мисля, че най-важното правило е винаги да се мисли на глас.

47
00:02:32,300 --> 00:02:36,980
Интервюто е трябвало да бъде вашият шанс да покаже процеса на мислене.

48
00:02:36,980 --> 00:02:39,820
Точка на интервюто е интервюиращият да се прецени

49
00:02:39,820 --> 00:02:42,660
начина, по който мислят и как ти мине през проблем.

50
00:02:42,660 --> 00:02:45,210
Най-лошото нещо, което може да направите, е да мълчат през цялото интервю.

51
00:02:45,210 --> 00:02:50,090
Това е просто не е добър.

52
00:02:50,090 --> 00:02:53,230
Когато даден въпрос, вие искате да се уверете, че сте разбрали въпроса.

53
00:02:53,230 --> 00:02:55,350
Така че повтарям въпроса в собствените си думи

54
00:02:55,350 --> 00:02:58,920
и се опитват да работят през няколко прости тестове

55
00:02:58,920 --> 00:03:01,530
да се уверете, че сте разбрали въпроса.

56
00:03:01,530 --> 00:03:05,510
Работа чрез няколко случая на изпитване също ще ви даде интуиция за това как да се реши този проблем.

57
00:03:05,510 --> 00:03:11,210
Може дори да се открият няколко модели, за да ви помогне да разрешите проблема.

58
00:03:11,210 --> 00:03:14,500
Тяхната най-голяма съвет е да не се разочароват.

59
00:03:14,500 --> 00:03:17,060
Не се разочароват.

60
00:03:17,060 --> 00:03:19,060
Интервютата са предизвикателство, но най-лошото нещо, което можеш да направиш,

61
00:03:19,060 --> 00:03:23,330
в допълнение да мълчи, е да бъдат видимо разочарован.

62
00:03:23,330 --> 00:03:27,410
Вие не искате да се даде такова впечатление на интервюиращия.

63
00:03:27,410 --> 00:03:33,960
Едно нещо, което - така, много хора, когато те отиват в интервю,

64
00:03:33,960 --> 00:03:37,150
те се опитват да се опитаме да намерим най-доброто решение за първи път,

65
00:03:37,150 --> 00:03:39,950
когато наистина има обикновено е напълно ясно решение.

66
00:03:39,950 --> 00:03:43,500
Тя може да е бавно, то може да бъде неефективна, но просто трябва да го заявя,

67
00:03:43,500 --> 00:03:46,210
само за да имате отправна точка, от която да работи по-добре.

68
00:03:46,210 --> 00:03:48,270
Също така, като посочи, решението е бавен, по отношение на

69
00:03:48,270 --> 00:03:52,160
Big O време сложност или сложност пространство,

70
00:03:52,160 --> 00:03:54,450
ще покаже на интервюиращия, че сте разбрали

71
00:03:54,450 --> 00:03:57,510
тези въпроси при писане на код.

72
00:03:57,510 --> 00:04:01,440
Така че не се страхува да излезе с най-простият алгоритъм първа

73
00:04:01,440 --> 00:04:04,950
и след това да работят по-добре от там.

74
00:04:04,950 --> 00:04:09,810
Всякакви въпроси досега? Добре.

75
00:04:09,810 --> 00:04:11,650
>> Така че нека да се потопите в първата наш проблем.

76
00:04:11,650 --> 00:04:14,790
"Като се има предвид масив от числа н, напишете функция, която разбърква масива

77
00:04:14,790 --> 00:04:20,209
на мястото, че всички пермутации на числа н са еднакво вероятни. "

78
00:04:20,209 --> 00:04:23,470
Предполагам, че имате на разположение един генератор на случайни число

79
00:04:23,470 --> 00:04:30,980
, което генерира цяло число в диапазона от 0, 1/2 кръг.

80
00:04:30,980 --> 00:04:32,970
Всички ли разбирам този въпрос?

81
00:04:32,970 --> 00:04:39,660
Аз ви давам масив от цели числа н, и аз искам да го претупвам.

82
00:04:39,660 --> 00:04:46,050
В моята директория, аз написах няколко програми, за да демонстрират какво искам да кажа.

83
00:04:46,050 --> 00:04:48,910
Отивам да се набутвам масив от 20 елемента,

84
00:04:48,910 --> 00:04:52,490
от -10 до 9,

85
00:04:52,490 --> 00:04:57,050
и аз искам да изведете списък като този.

86
00:04:57,050 --> 00:05:02,890
Така че това е моят подредени Входният масив, и аз искам да го претупвам.

87
00:05:02,890 --> 00:05:07,070
Ще го направим отново.

88
00:05:07,070 --> 00:05:13,780
Всички ли разбирам въпроса? Добре.

89
00:05:13,780 --> 00:05:16,730
Така че това е до вас.

90
00:05:16,730 --> 00:05:21,220
Какви са някои идеи? Можеш ли да го направя като N ^ 2, N дневник N, N?

91
00:05:21,220 --> 00:05:34,400
Отворени за предложения.

92
00:05:34,400 --> 00:05:37,730
Добре. Така една идея, предложена от Еми,

93
00:05:37,730 --> 00:05:45,300
е първото изчисляване на случайно число, произволно цяло число в диапазона 0-20.

94
00:05:45,300 --> 00:05:49,840
Така че поема нашия масив е с дължина от 20.

95
00:05:49,840 --> 00:05:54,800
В нашата диаграма от 20 елемента,

96
00:05:54,800 --> 00:05:58,560
това е нашата Входният масив.

97
00:05:58,560 --> 00:06:04,590
И сега, нейното предложение е да се създаде нов масив,

98
00:06:04,590 --> 00:06:08,440
така че това ще бъде изхода на масива.

99
00:06:08,440 --> 00:06:12,880
И въз основа се върнах от Ранд -

100
00:06:12,880 --> 00:06:17,580
така че, ако бях аз, да речем, 17,

101
00:06:17,580 --> 00:06:25,640
копирате 17-ти елемент в първата позиция.

102
00:06:25,640 --> 00:06:30,300
Сега ние трябва да изтриете - ние трябва да смени всички елементи тук

103
00:06:30,300 --> 00:06:36,920
над, така че имаме разминаване в края и няма дупки в средата.

104
00:06:36,920 --> 00:06:39,860
И сега ние повторете процеса.

105
00:06:39,860 --> 00:06:46,360
Сега изберете ново случайно число между 0 и 19.

106
00:06:46,360 --> 00:06:52,510
Имаме нов правя тук, и ние копирате този елемент в тази позиция.

107
00:06:52,510 --> 00:07:00,960
След това смени позиции и повторете процеса, докато ние имаме пълно нов масив.

108
00:07:00,960 --> 00:07:05,890
Какво е времето на работа на този алгоритъм?

109
00:07:05,890 --> 00:07:08,110
Е, нека да разгледаме въздействието на тази.

110
00:07:08,110 --> 00:07:10,380
Ние се изместват всеки елемент.

111
00:07:10,380 --> 00:07:16,800
Когато премахнем това аз, ние се изместват всички елементи след това наляво.

112
00:07:16,800 --> 00:07:21,600
А това е O (N) разходи

113
00:07:21,600 --> 00:07:26,100
защото това, което ако премахнем първия елемент?

114
00:07:26,100 --> 00:07:29,670
Така че при всяко преместване, ние премахваме -

115
00:07:29,670 --> 00:07:32,170
всяко преместване поема O (н) експлоатация,

116
00:07:32,170 --> 00:07:41,520
и тъй като ние сме N премествания, това води до O (N ^ 2) разбъркано.

117
00:07:41,520 --> 00:07:49,550
Добре. Толкова добър старт. Добро начало.

118
00:07:49,550 --> 00:07:55,290
>> Друго предложение е да се използва нещо, известно като претупвам Кнут,

119
00:07:55,290 --> 00:07:57,540
или Fisher-Йейтс разбъркване.

120
00:07:57,540 --> 00:07:59,630
И това е всъщност линейна разбъркано време.

121
00:07:59,630 --> 00:08:02,200
И идеята е много подобна.

122
00:08:02,200 --> 00:08:05,160
Отново, ние имаме Входният масив,

123
00:08:05,160 --> 00:08:08,580
но вместо да използват два масива за нашия вход / изход,

124
00:08:08,580 --> 00:08:13,590
ние използваме първата част на масива, за да следите разбъркват нашата част,

125
00:08:13,590 --> 00:08:18,400
и ние следим, а след това оставете останалото на нашата масив за unshuffled част.

126
00:08:18,400 --> 00:08:24,330
Така че, ето какво искам да кажа. Започваме с - ние избираме I,

127
00:08:24,330 --> 00:08:30,910
масив 0-20.

128
00:08:30,910 --> 00:08:36,150
Сегашната ни показалеца сочи първият индекс.

129
00:08:36,150 --> 00:08:39,590
Ние избираме някои тук

130
00:08:39,590 --> 00:08:42,740
и сега ние разменят.

131
00:08:42,740 --> 00:08:47,690
Така че, ако това е 5 и това беше 4,

132
00:08:47,690 --> 00:08:57,150
масив ще има 5 тук и 4.

133
00:08:57,150 --> 00:09:00,390
И сега ние отбелязваме маркер тук.

134
00:09:00,390 --> 00:09:05,770
Всичко в ляво се разменят

135
00:09:05,770 --> 00:09:15,160
и всичко, на дясно е unshuffled.

136
00:09:15,160 --> 00:09:17,260
И сега можем да повторим този процес.

137
00:09:17,260 --> 00:09:25,210
Ние избираме случаен индекс между 1 и 20.

138
00:09:25,210 --> 00:09:30,650
Така че предполагам, нашата нова съм тук.

139
00:09:30,650 --> 00:09:39,370
Сега ние суап това аз с текущата ни нова позиция тук.

140
00:09:39,370 --> 00:09:44,790
Така че правим смяна назад и напред по този начин.

141
00:09:44,790 --> 00:09:51,630
Нека ми донесе код, за да стане по-конкретна.

142
00:09:51,630 --> 00:09:55,290
Започваме с избора ни на и -

143
00:09:55,290 --> 00:09:58,370
започват с равен на 0, изберете произволно място J

144
00:09:58,370 --> 00:10:02,420
в unshuffled част на масива, аз до N-1.

145
00:10:02,420 --> 00:10:07,280
Така че, ако аз съм тук, изберете случаен индекс между тук и останалата част от масива,

146
00:10:07,280 --> 00:10:12,410
и ние суап.

147
00:10:12,410 --> 00:10:17,550
Това е код, необходим, за да разбъркате си масив.

148
00:10:17,550 --> 00:10:21,670
Някакви въпроси?

149
00:10:21,670 --> 00:10:25,530
>> Е, едно е необходимо въпрос е, защо е това е правилно?

150
00:10:25,530 --> 00:10:28,360
Защо е всяка пермутация еднакво вероятни?

151
00:10:28,360 --> 00:10:30,410
И аз няма да мине през доказателство за това,

152
00:10:30,410 --> 00:10:35,970
но много проблеми в компютърната наука може да бъде доказано чрез индукция.

153
00:10:35,970 --> 00:10:38,520
Колко от вас са запознати с индукция?

154
00:10:38,520 --> 00:10:40,590
Добре. Cool.

155
00:10:40,590 --> 00:10:43,610
Така че може да докаже верността на този алгоритъм с обикновено индукция,

156
00:10:43,610 --> 00:10:49,540
къде хипотеза индукция би било да приемем, че

157
00:10:49,540 --> 00:10:53,290
разбъркано ми се връща всяка пермутация еднакво вероятни

158
00:10:53,290 --> 00:10:56,120
до първите елементи I.

159
00:10:56,120 --> 00:10:58,300
Сега, помислете + 1.

160
00:10:58,300 --> 00:11:02,550
И от начина, по който ние избираме нашия J индекс за размяна,

161
00:11:02,550 --> 00:11:05,230
това води до - и след това да работите в детайли,

162
00:11:05,230 --> 00:11:07,390
най-малко един пълен доказателство за това защо този алгоритъм се връща

163
00:11:07,390 --> 00:11:12,800
всяка пермутация с еднаква вероятност вероятност.

164
00:11:12,800 --> 00:11:15,940
>> Добре, следващия проблем.

165
00:11:15,940 --> 00:11:19,170
Така "масив от цели числа, postive, нула, отрицателен,

166
00:11:19,170 --> 00:11:21,290
напишете функция, която изчислява максималната сума

167
00:11:21,290 --> 00:11:24,720
на всяка continueous subarray на входния масив.

168
00:11:24,720 --> 00:11:28,370
Пример тук е, че в случаите, когато всички числа са положителни,

169
00:11:28,370 --> 00:11:31,320
след това в момента е най-добрият избор е да се вземе целия масив.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, е равно на 10.

171
00:11:34,690 --> 00:11:36,780
Когато имате на някои негативи там,

172
00:11:36,780 --> 00:11:38,690
в този случай ние просто искаме първите две

173
00:11:38,690 --> 00:11:44,590
защото избора -1 и / или -3 ще донесе сумата.

174
00:11:44,590 --> 00:11:48,120
Понякога може да се наложи да започне в средата на масива.

175
00:11:48,120 --> 00:11:53,500
Понякога искаме да изберете нищо, то е най-добре да не вземат нищо.

176
00:11:53,500 --> 00:11:56,490
И понякога е по-добре да се вземат есента,

177
00:11:56,490 --> 00:12:07,510
, защото нещо, което след това е супер голям. Така че всякакви идеи?

178
00:12:07,510 --> 00:12:10,970
(Студент, неразбираем) >> Да.

179
00:12:10,970 --> 00:12:13,560
Да предположим, че аз не приемам -1.

180
00:12:13,560 --> 00:12:16,170
След това или да избера 1000 и 20000,

181
00:12:16,170 --> 00:12:18,630
или просто изберете от 3 милиарда.

182
00:12:18,630 --> 00:12:20,760
Е, най-добрият избор е да се вземат всички числа.

183
00:12:20,760 --> 00:12:24,350
Това -1, въпреки че е отрицателен,

184
00:12:24,350 --> 00:12:31,340
цялата сума е по-добре, отколкото аз да не предприемат -1.

185
00:12:31,340 --> 00:12:36,460
Така че един от съветите, които споменах по-рано е да се посочи ясно очевидно

186
00:12:36,460 --> 00:12:40,540
и груба сила решение на първо място.

187
00:12:40,540 --> 00:12:44,340
Какво е решение на грубата сила в този проблем? Да?

188
00:12:44,340 --> 00:12:46,890
[Джейн] Е, мисля, че грубата сила решение

189
00:12:46,890 --> 00:12:52,600
да се добавят всички възможни комбинации (неразбираемо).

190
00:12:52,600 --> 00:12:58,250
[Ю] Добре. Така че идеята на Джейн е да се вземат всички възможни

191
00:12:58,250 --> 00:13:01,470
Съм перифразиране - е да се вземат всички възможни непрекъснато subarray,

192
00:13:01,470 --> 00:13:07,840
изчисли си сума, а след това да се възползват максимално от всички възможни непрекъснати подмасива.

193
00:13:07,840 --> 00:13:13,310
Какво уникално идентифицира subarray в моя Входният масив?

194
00:13:13,310 --> 00:13:17,380
Например, две неща са ми нужни? Да?

195
00:13:17,380 --> 00:13:19,970
(Студент, неразбираем) >> Точно така.

196
00:13:19,970 --> 00:13:22,130
Долната граница на индекса и горна граница индекс

197
00:13:22,130 --> 00:13:28,300
еднозначно определя непрекъснато subarray.

198
00:13:28,300 --> 00:13:31,400
[Жена студент] Дали това е набор от уникални номера оцени?

199
00:13:31,400 --> 00:13:34,280
[Ю] Не Така че си въпрос, ние прие нашето масив -

200
00:13:34,280 --> 00:13:39,000
е нашият масив всички уникални номера, и отговорът е не.

201
00:13:39,000 --> 00:13:43,390
>> Ако се използва груба сила решение, а след това начало / край индекси

202
00:13:43,390 --> 00:13:47,200
еднозначно определя нашите непрекъснато subarray.

203
00:13:47,200 --> 00:13:51,680
Така че, ако за всички възможни записи стартиращи превъртите

204
00:13:51,680 --> 00:13:58,320
и за всички крайни записвания> или = да започне и <N,

205
00:13:58,320 --> 00:14:05,570
изчисли сумата и след това да вземем максималния размер на сумата, която сме виждали досега.

206
00:14:05,570 --> 00:14:07,880
Ясно ли е това?

207
00:14:07,880 --> 00:14:12,230
Какво е големият O на това решение?

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

209
00:14:16,660 --> 00:14:18,860
Не съвсем N ^ 2.

210
00:14:18,860 --> 00:14:25,250
Имайте предвид, че ние обхождане от 0 до N,

211
00:14:25,250 --> 00:14:27,520
така че това е един за контур.

212
00:14:27,520 --> 00:14:35,120
Ние отново обхождане почти от началото до края, за контур.

213
00:14:35,120 --> 00:14:37,640
И сега, в рамките на това, ние трябва да обобщим всяко влизане,

214
00:14:37,640 --> 00:14:43,810
така че това е друга линия. Така че ние имаме три вложени за вериги, N ^ 3.

215
00:14:43,810 --> 00:14:46,560
Добре. Това се отнася и като отправна точка.

216
00:14:46,560 --> 00:14:53,180
Нашето решение е не по-лошо от N ^ 3.

217
00:14:53,180 --> 00:14:55,480
Всички разбират ли решение на грубата сила?

218
00:14:55,480 --> 00:14:59,950
>> Добре. По-добро решение е използването на една идея, наречена динамично програмиране.

219
00:14:59,950 --> 00:15:03,040
Ако сте приели CS124, който е Алгоритми и структури от данни,

220
00:15:03,040 --> 00:15:05,680
вие ще станете много добре запознати с тази техника.

221
00:15:05,680 --> 00:15:12,190
И идеята е, че се опитват да изградят решения на по-малки проблеми.

222
00:15:12,190 --> 00:15:17,990
Какво искам да кажа от това е, ние в момента трябва да се притеснявате за две неща: начало и край.

223
00:15:17,990 --> 00:15:29,340
И това е досадно. Какво ще стане, ако можем да се отърве от един от тези параметри?

224
00:15:29,340 --> 00:15:32,650
Една от идеите е да - ние нашата оригинална проблем,

225
00:15:32,650 --> 00:15:37,470
намерите максимален размер от всяко subarray в диапазона [O, N-1].

226
00:15:37,470 --> 00:15:47,400
И сега имаме нов subproblem, където знаем, в сегашния ни и индекс

227
00:15:47,400 --> 00:15:52,520
ние знаем, че трябва да сключи. Нашата subarray трябва да сложи край на текущия индекс.

228
00:15:52,520 --> 00:15:57,640
Така оставащ проблем е, когато трябва да започнем нашата subarray?

229
00:15:57,640 --> 00:16:05,160
Това прави ли смисъл? Добре.

230
00:16:05,160 --> 00:16:12,030
Така че аз съм кодирана нещата, и нека да погледнем какво означава това.

231
00:16:12,030 --> 00:16:16,230
В codirectory, има програма, наречена subarray,

232
00:16:16,230 --> 00:16:19,470
и отнема броя на елементите,

233
00:16:19,470 --> 00:16:25,550
и го връща на максимална сума subarray в разбъркват моя списък.

234
00:16:25,550 --> 00:16:29,920
Така че в този случай, максимално subarray е 3.

235
00:16:29,920 --> 00:16:34,850
И това е само с помощта на 2 и 1.

236
00:16:34,850 --> 00:16:38,050
Нека да се кандидатира отново. Това е също 3.

237
00:16:38,050 --> 00:16:40,950
Но този път, обърнете внимание как ние имаме 3.

238
00:16:40,950 --> 00:16:46,690
Взехме - ние просто приемете три себе си

239
00:16:46,690 --> 00:16:49,980
, тъй като е заобиколен от негативите от двете страни,

240
00:16:49,980 --> 00:16:55,080
което ще доведе до сума <3.

241
00:16:55,080 --> 00:16:57,820
Да се ​​движат по 10 позиции.

242
00:16:57,820 --> 00:17:03,200
Този път това е 7, ние да поеме водеща 3 и 4.

243
00:17:03,200 --> 00:17:09,450
Този път това е 8, а ние получаваме, че, като 1, 4 и 3.

244
00:17:09,450 --> 00:17:16,310
Така че, за да ви даде интуиция за това как можем да решим този променен проблем,

245
00:17:16,310 --> 00:17:18,890
нека да погледнем на този subarray.

246
00:17:18,890 --> 00:17:23,460
Ние сме този вход масив, и ние знаем, отговорът е 8.

247
00:17:23,460 --> 00:17:26,359
Ние приемаме 1, 4 и 3.

248
00:17:26,359 --> 00:17:29,090
Но нека да разгледаме как ние всъщност този отговор.

249
00:17:29,090 --> 00:17:34,160
Нека да погледнем в максимална subarray, което сложи край на всеки от тези показатели.

250
00:17:34,160 --> 00:17:40,780
Каква е максималната subarray, което трябва да завърши на първо място?

251
00:17:40,780 --> 00:17:46,310
[Student] нула. >> Zero. Само не приемайте -5.

252
00:17:46,310 --> 00:17:50,210
Тук ще бъде 0, както и. Да?

253
00:17:50,210 --> 00:17:56,470
(Студент, неразбираемо)

254
00:17:56,470 --> 00:17:58,960
[Ю] О, съжалявам, това е -3.

255
00:17:58,960 --> 00:18:03,220
Така че това е 2, това е -3.

256
00:18:03,220 --> 00:18:08,690
Добре. Така -4, каква е максималната subarray до края на тази позиция

257
00:18:08,690 --> 00:18:12,910
където -4 е? Zero.

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

259
00:18:22,570 --> 00:18:28,060
Сега, аз трябва да се сложи край на мястото, където -2 е.

260
00:18:28,060 --> 00:18:39,330
Така 6, 5, 7, и последният е 4.

261
00:18:39,330 --> 00:18:43,480
Знаейки, че това са моите записи

262
00:18:43,480 --> 00:18:48,130
трансформира проблем, когато аз трябва да приключат на всеки един от тези показатели,

263
00:18:48,130 --> 00:18:51,410
след последната ми отговор е просто да из целия

264
00:18:51,410 --> 00:18:53,580
и да вземат максималния им брой.

265
00:18:53,580 --> 00:18:55,620
Така че в този случай това е 8.

266
00:18:55,620 --> 00:19:00,010
Това означава,, че максималният subarray завършва в този индекс,

267
00:19:00,010 --> 00:19:04,970
и започна някъде пред него.

268
00:19:04,970 --> 00:19:09,630
Всички ли разбирам този променен subarray?

269
00:19:09,630 --> 00:19:22,160
>> Добре. Ами, нека да разбера повтаряне за това.

270
00:19:22,160 --> 00:19:27,990
Нека разгледаме само първите няколко вписвания.

271
00:19:27,990 --> 00:19:35,930
Така че тук е 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
И тогава там е -2 тук, и че го свалиха до 6.

273
00:19:39,790 --> 00:19:50,800
Така че, ако аз наричам влизане в позиция subproblem (I),

274
00:19:50,800 --> 00:19:54,910
как мога да използвам отговор на предишна subproblem

275
00:19:54,910 --> 00:19:59,360
да отговори на тази subproblem?

276
00:19:59,360 --> 00:20:04,550
Ако гледам, нека кажем, този пост.

277
00:20:04,550 --> 00:20:09,190
Как мога да се изчисли отговор 6, като погледнете в

278
00:20:09,190 --> 00:20:18,780
комбинация от този масив и отговори на предишни subproblems в този масив? Да?

279
00:20:18,780 --> 00:20:22,800
[Жена студент] масива на суми

280
00:20:22,800 --> 00:20:25,430
в състояние преди, така че 8

281
00:20:25,430 --> 00:20:32,170
и след това да добавите настоящата subproblem.

282
00:20:32,170 --> 00:20:36,460
[Ю] Така че нейното предложение е да се погледне на тези две числа,

283
00:20:36,460 --> 00:20:40,090
този номер и този номер.

284
00:20:40,090 --> 00:20:50,130
Така че това 8 се отнася до отговора за subproblem (I - 1).

285
00:20:50,130 --> 00:20:57,300
И нека го наречем моя масив вход А.

286
00:20:57,300 --> 00:21:01,470
За да се намери максимален subarray, който завършва и позиция,

287
00:21:01,470 --> 00:21:03,980
Имам две възможности: Мога да продължи subarray

288
00:21:03,980 --> 00:21:09,790
, която приключи в предишния индекс, или започнете нов масив.

289
00:21:09,790 --> 00:21:14,190
Ако аз трябваше да продължи subarray, която започна в предишния индекс,

290
00:21:14,190 --> 00:21:19,260
тогава максималната сума, може да се постигне, е отговорът на предишния subproblem

291
00:21:19,260 --> 00:21:24,120
плюс масив влизане.

292
00:21:24,120 --> 00:21:27,550
Но, аз също имам избор за стартиране на нов subarray

293
00:21:27,550 --> 00:21:30,830
като в този случай сумата е 0.

294
00:21:30,830 --> 00:21:42,860
Така че отговорът е макс на 0, subproblem и - 1, плюс текущия елемент от масива.

295
00:21:42,860 --> 00:21:46,150
Ли това повторение има ли смисъл?

296
00:21:46,150 --> 00:21:50,840
Нашата рецидив, тъй като ние току-що открих, е subproblem и

297
00:21:50,840 --> 00:21:54,740
е равна на максимум предходната subproblem плюс текущата ми елемент от масива,

298
00:21:54,740 --> 00:22:01,490
което означава, продължи предишната subarray,

299
00:22:01,490 --> 00:22:07,250
или 0, започнете нова subarray в сегашния си индекс.

300
00:22:07,250 --> 00:22:10,060
И след като сме изградили тази таблица на решения, тогава нашият окончателен отговор,

301
00:22:10,060 --> 00:22:13,950
просто правя линейна размах през subproblem масив

302
00:22:13,950 --> 00:22:19,890
и да вземат максималния им брой.

303
00:22:19,890 --> 00:22:23,330
Това е точното прилагане на това, което току-що казах.

304
00:22:23,330 --> 00:22:27,320
Така че ние създаваме нов масив subproblem, subproblems.

305
00:22:27,320 --> 00:22:32,330
Първият запис е 0 или на първото влизане, максималното от тези две.

306
00:22:32,330 --> 00:22:35,670
А за останалата част от subproblems

307
00:22:35,670 --> 00:22:39,810
ние използваме точно повторение, ние току-що открих.

308
00:22:39,810 --> 00:22:49,960
Сега ние се изчисли максимум на нашата subproblems масив, и това е нашият окончателен отговор.

309
00:22:49,960 --> 00:22:54,130
>> Така че колко пространство се използва в този алгоритъм?

310
00:22:54,130 --> 00:23:01,470
Ако сте само CS50, тогава може и да не са обсъждали пространство много.

311
00:23:01,470 --> 00:23:07,750
Е, едно нещо, което трябва да се отбележи, е, че се обадих на изчистване тук с размер N.

312
00:23:07,750 --> 00:23:13,590
Какво значи това ви предложа?

313
00:23:13,590 --> 00:23:17,450
Този алгоритъм използва линейно пространство.

314
00:23:17,450 --> 00:23:21,030
Можем ли да направим по-добре?

315
00:23:21,030 --> 00:23:30,780
Има ли нещо, което забележите, че не е необходимо да се изчисли окончателен отговор?

316
00:23:30,780 --> 00:23:33,290
Предполагам, че по-добрият въпрос е, каква информация

317
00:23:33,290 --> 00:23:40,680
не трябва да носят през целия път до края?

318
00:23:40,680 --> 00:23:44,280
Сега, ако се вгледаме в тези две линии,

319
00:23:44,280 --> 00:23:47,720
ние само се грижи за предишния subproblem,

320
00:23:47,720 --> 00:23:50,910
и ние само се грижи за максималното, което сме виждали досега.

321
00:23:50,910 --> 00:23:53,610
За да се изчисли окончателен отговор, ние не се нуждаем от целия масив.

322
00:23:53,610 --> 00:23:57,450
Нужно е само по последната цифра, последните две цифри.

323
00:23:57,450 --> 00:24:02,630
На последния номер за subproblem масив, и последното число за максималната.

324
00:24:02,630 --> 00:24:07,380
Така че, всъщност, ние можем да се слеят тези вериги

325
00:24:07,380 --> 00:24:10,460
и си отиват от линейно пространство до постоянно пространство.

326
00:24:10,460 --> 00:24:15,830
Текущ сумата досега, тук, замества ролята на subproblem, нашата subproblem масив.

327
00:24:15,830 --> 00:24:20,020
Така че сегашната сума, доколкото е отговорът на предишния subproblem.

328
00:24:20,020 --> 00:24:23,450
И тази сума, досега, заема мястото на нашата макс.

329
00:24:23,450 --> 00:24:28,100
Изчисляваме максимално, като отидем заедно.

330
00:24:28,100 --> 00:24:30,890
И така преминаваме от линейно пространство на постоянно място,

331
00:24:30,890 --> 00:24:36,650
и ние също трябва линейна решение на проблема ни subarray.

332
00:24:36,650 --> 00:24:40,740
>> Тези въпроси ще получите по време на интервю.

333
00:24:40,740 --> 00:24:44,450
Какво е времето сложност; какво е пространството сложност?

334
00:24:44,450 --> 00:24:50,600
Можеш ли да направиш по-добре? Има ли неща, които не са необходими, за да се запази около?

335
00:24:50,600 --> 00:24:55,270
Аз направих това, за да се подчертае анализи, които трябва да вземете по своему

336
00:24:55,270 --> 00:24:57,400
като работим чрез тези проблеми.

337
00:24:57,400 --> 00:25:01,710
Винаги си задавайте въпроса: "Мога ли да направя по-добре?"

338
00:25:01,710 --> 00:25:07,800
В действителност, можем да направим по-добро от това?

339
00:25:07,800 --> 00:25:10,730
Сортиране на подвеждащ въпрос. Не можеш, защото трябва да се

340
00:25:10,730 --> 00:25:13,590
поне прочетете входа на проблема.

341
00:25:13,590 --> 00:25:15,570
Така че самият факт, че трябва да най-малко четат входа на проблема

342
00:25:15,570 --> 00:25:19,580
означава, че не можеш да направиш по-добре, отколкото линейно време,

343
00:25:19,580 --> 00:25:22,870
и не можеш да направиш по-добре в сравнение с постоянния пространство.

344
00:25:22,870 --> 00:25:27,060
Така че това е, всъщност, най-доброто решение на този проблем.

345
00:25:27,060 --> 00:25:33,040
Въпроси? Добре.

346
00:25:33,040 --> 00:25:35,190
>> Проблем на фондовия пазар:

347
00:25:35,190 --> 00:25:38,350
"Като се има предвид масив от цели числа N, положителни, нулеви или отрицателни,

348
00:25:38,350 --> 00:25:41,680
, които представляват цената на фондовата н ден,

349
00:25:41,680 --> 00:25:44,080
напиши функция за изчисляване на максимална печалба, можете да направите

350
00:25:44,080 --> 00:25:49,350
като се има предвид, че купуват и продават точно един състав в рамките на тези н ден. "

351
00:25:49,350 --> 00:25:51,690
По същество, ние искаме да купуват ниско, продават големи.

352
00:25:51,690 --> 00:25:58,580
И ние искаме да измислят най-добрата печалба, можем да направим.

353
00:25:58,580 --> 00:26:11,500
Връщайки се към върха ми, това, което е непосредствено ясно, простият отговор, но това е бавен?

354
00:26:11,500 --> 00:26:17,690
Да? (Студент, неразбираем) >> Да.

355
00:26:17,690 --> 00:26:21,470
>> Така че просто ще отида все пак и погледнете цените на акциите

356
00:26:21,470 --> 00:26:30,550
във всяка точка във времето (неразбираемо).

357
00:26:30,550 --> 00:26:33,990
[Ю] Добре, така че нейният решение - предложение на изчислителната техника

358
00:26:33,990 --> 00:26:37,380
най-ниската и изчисляване на най-високата не е задължително да работи

359
00:26:37,380 --> 00:26:42,470
тъй като най-високото може да се случи преди най-ниската.

360
00:26:42,470 --> 00:26:47,340
Така че това, което е груба сила решение на този проблем?

361
00:26:47,340 --> 00:26:53,150
Какви са двете неща, които трябва да може еднозначно да се определи печалбата правя? Точно така.

362
00:26:53,150 --> 00:26:59,410
Груба сила е решение - О, значи, предложение Джордж е само нужда от два дни

363
00:26:59,410 --> 00:27:02,880
за да може еднозначно да се определи печалбата на тези два дни.

364
00:27:02,880 --> 00:27:06,660
Така че ние се изчислява всеки чифт, като купува / продава

365
00:27:06,660 --> 00:27:12,850
изчисли печалбата, която може да бъде отрицателен или положителен или нулев.

366
00:27:12,850 --> 00:27:18,000
Изчислете максимална печалба, че ние правим след итерации над всички двойки на ден.

367
00:27:18,000 --> 00:27:20,330
Това ще бъде нашият окончателен отговор.

368
00:27:20,330 --> 00:27:25,730
И това решение ще бъде O (N ^ 2), защото има N изберете два чифта -

369
00:27:25,730 --> 00:27:30,270
на ден, които можете да избирате сред крайните ден.

370
00:27:30,270 --> 00:27:32,580
Добре, така че аз не отивам тук да премине груба сила решение.

371
00:27:32,580 --> 00:27:37,420
Аз ще ви кажа, че има N дневник N решение.

372
00:27:37,420 --> 00:27:45,550
Какво алгоритъм момента знаем, че е н дневник н?

373
00:27:45,550 --> 00:27:50,730
Това не е подвеждащ въпрос.

374
00:27:50,730 --> 00:27:54,790
>> Обединяване вид. Обединяване вид е н н дневник,

375
00:27:54,790 --> 00:27:57,760
и в действителност, един от начините за решаване на този проблем е да се използва

376
00:27:57,760 --> 00:28:04,400
един вид сливане на идея, наречена, като цяло, разделяй и владей.

377
00:28:04,400 --> 00:28:07,570
И идеята е, както следва.

378
00:28:07,570 --> 00:28:12,400
Искаш ли да се изчисли най-добрите купува / продава двойка в лявата половина.

379
00:28:12,400 --> 00:28:16,480
Намерете най-добрите печалбата, която могат да направят, само с първия N в рамките на два дни.

380
00:28:16,480 --> 00:28:19,780
След искате да oompute най-добрите купува / продава чифт върху дясната половина,

381
00:28:19,780 --> 00:28:23,930
Така последната N в рамките на два дни.

382
00:28:23,930 --> 00:28:32,400
И сега въпросът е, как да се слеят тези решения отново заедно?

383
00:28:32,400 --> 00:28:36,320
Да? (Студент, неразбираемо)

384
00:28:36,320 --> 00:28:49,890
>> Добре. Така че нека да нарисува картина.

385
00:28:49,890 --> 00:29:03,870
Да? (Джордж, неразбираем)

386
00:29:03,870 --> 00:29:06,450
>> Точно така. Джордж решение е точно така.

387
00:29:06,450 --> 00:29:10,040
Така че предложението му е първото изчисляване на най-добрата двойка купува / продава

388
00:29:10,040 --> 00:29:16,050
и че се появява в лявата половина, така че нека го наречем, че ляво, ляво.

389
00:29:16,050 --> 00:29:20,790
Най-добър купува / продава двойка, която се появява в дясната половина.

390
00:29:20,790 --> 00:29:25,180
Но ако ние само спрямо тези две числа, ни липсва по делото

391
00:29:25,180 --> 00:29:30,460
където ние купуваме тук и продават някъде в дясната половина.

392
00:29:30,460 --> 00:29:33,810
Ние купуваме в лявата половина продават в дясната половина.

393
00:29:33,810 --> 00:29:38,490
И най-добрият начин да се изчисли най-добрите купува / продава чифт, който обхваща двете полувремена

394
00:29:38,490 --> 00:29:43,480
е да се пресметнат минимум тук и изчисляване на максималната тук

395
00:29:43,480 --> 00:29:45,580
и да им разлика.

396
00:29:45,580 --> 00:29:50,850
Така двете случаите, когато двойката купува / продава се случва само тук,

397
00:29:50,850 --> 00:30:01,910
само тук, или на двете полувремена се определя от тези три числа.

398
00:30:01,910 --> 00:30:06,450
Така че нашият алгоритъм, за да се слеят нашите решения,

399
00:30:06,450 --> 00:30:08,350
искаме да се изчисли най-добрата двойка купува / продава

400
00:30:08,350 --> 00:30:13,120
където ние купуваме в лявата половина и продават в дясната половина.

401
00:30:13,120 --> 00:30:16,740
И най-добрият начин да направите това е да се изчисли най-ниската цена в първата половина,

402
00:30:16,740 --> 00:30:20,360
най-високата цена в дясната половина, и да си вземат разликата.

403
00:30:20,360 --> 00:30:25,390
В резултат на три печалби, тези три числа, се възползват максимално от трите,

404
00:30:25,390 --> 00:30:32,720
и това е най-добрата печалба може да се направи през тези първи и в края ден.

405
00:30:32,720 --> 00:30:36,940
Ето най-важните линии са в червено.

406
00:30:36,940 --> 00:30:41,160
Това е рекурсивно повикване, за да се изчисли отговор в лявата половина.

407
00:30:41,160 --> 00:30:44,760
Това е рекурсивно повикване, за да се изчисли отговор в дясната половина.

408
00:30:44,760 --> 00:30:50,720
Тези две за вериги изчисли мин и макс на лявата и дясната половина.

409
00:30:50,720 --> 00:30:54,970
Сега се изчисли печалбата, която обхваща двете полувремена,

410
00:30:54,970 --> 00:31:00,530
и окончателен отговор е максималната от тези три.

411
00:31:00,530 --> 00:31:04,120
Добре.

412
00:31:04,120 --> 00:31:06,420
>> Така че, разбира се, ние имаме един алгоритъм, но големият въпрос е,

413
00:31:06,420 --> 00:31:08,290
какво е времето сложността на този въпрос?

414
00:31:08,290 --> 00:31:16,190
И причината, поради която споменах сливане вид е, че тази форма на разделяме отговор

415
00:31:16,190 --> 00:31:19,200
на две и след това обединяване на нашите решения заедно

416
00:31:19,200 --> 00:31:23,580
е точно формата на сливане вид.

417
00:31:23,580 --> 00:31:33,360
Така че нека да мине през продължителността.

418
00:31:33,360 --> 00:31:41,340
Ако ние определено функция т (н) да бъде броя на стъпките

419
00:31:41,340 --> 00:31:50,010
N за ден,

420
00:31:50,010 --> 00:31:54,350
нашите две рекурсивни повиквания

421
00:31:54,350 --> 00:32:00,460
всеки ще струва тон (N / 2),

422
00:32:00,460 --> 00:32:03,540
и има два от тези разговори.

423
00:32:03,540 --> 00:32:10,020
Сега трябва да се изчисли минимум на лявата половина,

424
00:32:10,020 --> 00:32:17,050
, което мога да направя в N / 2 време, плюс максимум на дясната половина.

425
00:32:17,050 --> 00:32:20,820
Така че това е просто N.

426
00:32:20,820 --> 00:32:25,050
И тогава, плюс някои постоянна работа.

427
00:32:25,050 --> 00:32:27,770
И това повторение уравнение

428
00:32:27,770 --> 00:32:35,560
е точно повторение уравнението за сливане вид.

429
00:32:35,560 --> 00:32:39,170
И ние всички знаем, че се сливат вид е н дневник н време.

430
00:32:39,170 --> 00:32:46,880
Затова нашият алгоритъм е N дневник н.

431
00:32:46,880 --> 00:32:52,220
Ли тази итерация има ли смисъл?

432
00:32:52,220 --> 00:32:55,780
Само една кратка рекапитулация на това:

433
00:32:55,780 --> 00:32:59,170
T (N) е броя на стъпките за изчисляване на максимална печалба

434
00:32:59,170 --> 00:33:02,750
в течение N на ден.

435
00:33:02,750 --> 00:33:06,010
Начинът, по който се разделят нашите рекурсивни повиквания

436
00:33:06,010 --> 00:33:11,980
е като се обадите на нашето решение на първия ден N / 2,

437
00:33:11,980 --> 00:33:14,490
така че това е един разговор,

438
00:33:14,490 --> 00:33:16,940
и след това ние наричаме отново на второто полувреме.

439
00:33:16,940 --> 00:33:20,440
Така че това е двете повиквания.

440
00:33:20,440 --> 00:33:25,310
И тогава ние откриваме минимум в лявата половина, което можем да направим в линейното време,

441
00:33:25,310 --> 00:33:29,010
намерите максимум на дясната половина, което можем да направим в линейното време.

442
00:33:29,010 --> 00:33:31,570
Така N / 2 + N / 2 е просто н.

443
00:33:31,570 --> 00:33:36,020
Тогава ние имаме някаква постоянна работа, което е като смятане.

444
00:33:36,020 --> 00:33:39,860
Този рецидив уравнение е точно повторение уравнението за сливане вид.

445
00:33:39,860 --> 00:33:55,490
Следователно, разбъркано алгоритъм е N влезете н.

446
00:33:55,490 --> 00:33:58,520
Така че, колко място ще използвате?

447
00:33:58,520 --> 00:34:04,910
Нека се върнем на кода.

448
00:34:04,910 --> 00:34:09,420
>> По-добрият въпрос е, колко стека рамки ние някога в даден момент?

449
00:34:09,420 --> 00:34:11,449
Тъй като ние сме използване на рекурсия,

450
00:34:11,449 --> 00:34:23,530
броя на стека рамки определя използването на нашето пространство.

451
00:34:23,530 --> 00:34:29,440
Нека разгледаме N = 8.

452
00:34:29,440 --> 00:34:36,889
Ние наричаме разбъркването 8,

453
00:34:36,889 --> 00:34:41,580
, които ще се обадя на разбъркването първите четири записа,

454
00:34:41,580 --> 00:34:46,250
, които ще се обадя на разбъркването първите два записа.

455
00:34:46,250 --> 00:34:51,550
Така че нашата стак е - това е нашата стека.

456
00:34:51,550 --> 00:34:54,980
И тогава ние наричаме набутвам отново на 1,

457
00:34:54,980 --> 00:34:58,070
и това е, което нашата база случай е, за да се върнем веднага.

458
00:34:58,070 --> 00:35:04,700
Ли някога повече от това много рамки стека?

459
00:35:04,700 --> 00:35:08,880
Не, защото всеки път, когато правим позоваването

460
00:35:08,880 --> 00:35:10,770
рекурсивно извикване, за да претупвам,

461
00:35:10,770 --> 00:35:13,950
ние разделяме нашия размер на половина.

462
00:35:13,950 --> 00:35:17,020
Така максималният брой на стека рамки някога във всеки един момент

463
00:35:17,020 --> 00:35:28,460
е по нареждане на Дневник н стека рамки.

464
00:35:28,460 --> 00:35:42,460
Всеки стек рамка има постоянна пространство,

465
00:35:42,460 --> 00:35:44,410
и следователно общата сума на пространството,

466
00:35:44,410 --> 00:35:49,240
максималния размер на пространството, което някога използвате е O (дневник н) пространство

467
00:35:49,240 --> 00:36:03,040
където N е броя на дните.

468
00:36:03,040 --> 00:36:07,230
>> Сега, винаги се запитате, "Можем ли да направя по-добре?"

469
00:36:07,230 --> 00:36:12,390
И по-специално, можем да се намали този проблем, вече сме решени?

470
00:36:12,390 --> 00:36:20,040
Жокер: само обсъди две други проблеми преди това, и това няма да се набутвам.

471
00:36:20,040 --> 00:36:26,200
Ние можем да конвертирате този проблем фондов пазар в максималната проблем subarray.

472
00:36:26,200 --> 00:36:40,100
Как можем да направим това?

473
00:36:40,100 --> 00:36:42,570
Един от вас? Еми?

474
00:36:42,570 --> 00:36:47,680
(Еми, неразбираем)

475
00:36:47,680 --> 00:36:53,860
[Ю] Точно така.

476
00:36:53,860 --> 00:36:59,940
Така максималната проблем subarray

477
00:36:59,940 --> 00:37:10,610
търсим сума непрекъснато subarray.

478
00:37:10,610 --> 00:37:16,230
И предложение на "Еми" за проблема с запаси,

479
00:37:16,230 --> 00:37:30,720
разгледа промени, или делта.

480
00:37:30,720 --> 00:37:37,440
И картина на това е - това е цената на запаси,

481
00:37:37,440 --> 00:37:42,610
но ако вземем разликата между всеки пореден ден -

482
00:37:42,610 --> 00:37:45,200
така че ние виждаме, че максималната цена, максимална печалба можем да направим

483
00:37:45,200 --> 00:37:50,070
е, ако ние купуваме тук и продават тук.

484
00:37:50,070 --> 00:37:54,240
Но нека да разгледаме в непрекъснат нека погледнем в subarray проблем.

485
00:37:54,240 --> 00:38:02,510
Така че тук, можем да направим - от тук до тук,

486
00:38:02,510 --> 00:38:08,410
имаме положителна промяна, и след това става от тук до тук имаме отрицателна промяна.

487
00:38:08,410 --> 00:38:14,220
Но след това, от тук до тук имаме огромна положителна промяна.

488
00:38:14,220 --> 00:38:20,930
И това са промените, които искаме да обобщим, за да получите нашата крайна печалба.

489
00:38:20,930 --> 00:38:25,160
Тогава ние имаме по-негативни промени тук.

490
00:38:25,160 --> 00:38:29,990
Ключът към намаляване на нашия състав проблем в максимална subarray проблем

491
00:38:29,990 --> 00:38:36,630
е да се разгледа делтите между дни.

492
00:38:36,630 --> 00:38:40,630
Така че ние създаваме нов масив наречен делти,

493
00:38:40,630 --> 00:38:43,000
инициализиране на първото влизане, за да бъде 0,

494
00:38:43,000 --> 00:38:46,380
и след това за всяка делта (I), нека това да бъде разликата

495
00:38:46,380 --> 00:38:52,830
Входният масив (I), и масив (I - 1).

496
00:38:52,830 --> 00:38:55,530
Тогава ние наричаме нашия рутинна процедура за максимално subarray

497
00:38:55,530 --> 00:39:01,500
преминаващи в масив на делтата.

498
00:39:01,500 --> 00:39:06,440
И тъй като максимално subarray е линейното време,

499
00:39:06,440 --> 00:39:09,370
и това намаление, този процес на създаването на тази делта масив,

500
00:39:09,370 --> 00:39:11,780
е линейно време,

501
00:39:11,780 --> 00:39:19,060
след окончателното решение за запаси е O (N) работа плюс O (N) работа, все още е O (N) работа.

502
00:39:19,060 --> 00:39:23,900
Така че ние имаме линейно решение на нашия проблем.

503
00:39:23,900 --> 00:39:29,610
Всички ли разбирам тази трансформация?

504
00:39:29,610 --> 00:39:32,140
>> Като цяло, добра идея, която винаги трябва да има

505
00:39:32,140 --> 00:39:34,290
се опитат да намалят нов проблем, който вие виждате.

506
00:39:34,290 --> 00:39:37,700
Ако изглежда познат на един стар проблем,

507
00:39:37,700 --> 00:39:39,590
опитайте се да го намали до един стар проблем.

508
00:39:39,590 --> 00:39:41,950
И ако може да използваме всички инструменти, които сте използвали по стар проблем

509
00:39:41,950 --> 00:39:46,450
за решаване на нов проблем.

510
00:39:46,450 --> 00:39:49,010
Така че, за да се приключи, технически интервюта оспорват.

511
00:39:49,010 --> 00:39:52,280
Тези проблеми вероятно са някои от най-трудните проблеми

512
00:39:52,280 --> 00:39:54,700
, които можете да видите в интервю,

513
00:39:54,700 --> 00:39:57,690
така че, ако вие не разбирате всички проблеми, които аз просто обхванати, всичко е наред.

514
00:39:57,690 --> 00:40:01,080
Това са някои от най-трудните проблеми.

515
00:40:01,080 --> 00:40:03,050
Практика, практика, практика.

516
00:40:03,050 --> 00:40:08,170
Дадох много проблеми в помагалото, така че определено проверите тези.

517
00:40:08,170 --> 00:40:11,690
И късмет на вашите интервюта. Всичките ми средства са публикувани в тази връзка,

518
00:40:11,690 --> 00:40:15,220
и един от моите старши приятели предложи да се направи макет технически интервюта,

519
00:40:15,220 --> 00:40:22,050
така че ако ви интересува, електронна поща, ще Яо този имейл адрес.

520
00:40:22,050 --> 00:40:26,070
Ако имате някакви въпроси, можете да ме питате.

521
00:40:26,070 --> 00:40:28,780
Вие, момчета, имате ли конкретни въпроси, свързани с технически интервюта

522
00:40:28,780 --> 00:40:38,440
или някакви проблеми, които сме виждали досега?

523
00:40:38,440 --> 00:40:49,910
Добре. Е, на добър час на вашите интервюта.

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