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

2
00:00:02,640 --> 00:00:04,630
[Kenny Ю., Гарвардский университет]

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, и я бы хотел этого, когда я был студент первого или второго курса,

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
Структура интервью постион разработки программного обеспечения,

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
Интервью себе, как правило, 2 или 3 проблемы

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
они будут просить вас, вроде бы, сколько времени и пространстве сложность, большие 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
большое время 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 до я, половину диапазона.

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
Какие идеи? Вы можете сделать это при п ^ 2, п § п, п?

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 (п) стоимость

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 (N) операций,

116
00:07:32,170 --> 00:07:41,520
и так как мы имеем п абсорбции, это приводит к 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-Yates Shuffle.

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
Итак, вот что я имею в виду. Мы начинаем с - мы выбираем я,

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 часть массива, я до п-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
до первого элемента я.

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 подмассива входной массив ".

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
Я перефразирую - это принять все возможные непрерывной подмассива,

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

193
00:13:07,840 --> 00:13:13,310
Что однозначно идентифицирует подмассива в моей входной массив?

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
однозначно определяет непрерывную подмассива.

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
однозначно определяет наши постоянные подмассива.

203
00:13:47,200 --> 00:13:51,680
Поэтому, если мы перебора всех возможных записей начала,

204
00:13:51,680 --> 00:13:58,320
и для всех конечных элементов> или =, чтобы начать, и <п,

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
Что такое большое О от этого решения?

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 до п,

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
так что это еще один цикл. Таким образом, мы имеем три вложенные циклы, п ^ 3.

215
00:14:43,810 --> 00:14:46,560
Хорошо. Это идет в качестве отправной точки.

216
00:14:46,560 --> 00:14:53,180
Наше решение не хуже, чем п ^ 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
Одна из идей заключается - we're учитывая нашу исходную задачу,

225
00:15:32,650 --> 00:15:37,470
найти максимальную сумму любых подмассива в диапазоне [О, N-1].

226
00:15:37,470 --> 00:15:47,400
И теперь у нас есть новый подзадачи, где мы знаем, в нашей текущей индекс г,

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

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

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, есть программа под названием подмассива,

232
00:16:16,230 --> 00:16:19,470
и он принимает число элементов,

233
00:16:19,470 --> 00:16:25,550
и возвращает максимальную сумму подмассива в моем списке перемешиваются.

234
00:16:25,550 --> 00:16:29,920
Таким образом, в этом случае, наш максимальный подмассива равен 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
Мы взяли - мы просто возьмем 3-сам

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
Давайте взглянем на эту подмассива.

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
Давайте посмотрим на максимальной подмассива, который закончился на каждый из этих показателей.

250
00:17:34,160 --> 00:17:40,780
Какой максимальный подмассива, который должен закончиться на первой позиции?

251
00:17:40,780 --> 00:17:46,310
[Студент] Zero. >> 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, что максимальная подмассива до конца, что положение

257
00:18:08,690 --> 00:18:12,910
-4, где находится? Zero.

258
00:18:12,910 --> 00:18:22,570
Один? 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
Это означает, что максимальная подмассива заканчивается в этом индексе,

267
00:19:00,010 --> 00:19:04,970
и начал где-то перед ним.

268
00:19:04,970 --> 00:19:09,630
Все ли понимают это превращается подмассива?

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
Так что, если я называю вступления в должность я подзадача (I),

274
00:19:50,800 --> 00:19:54,910
как я могу использовать ответе на предыдущий подзадачи

275
00:19:54,910 --> 00:19:59,360
Для ответа на этот подзадачи?

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
Сочетание этого массива и ответов на предыдущие подзадач в этом массиве? Да?

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
а затем добавить текущую подзадачи.

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 относится к ответом на подзадачи (я - 1).

285
00:20:50,130 --> 00:20:57,300
И давайте называть моего входного массива A.

286
00:20:57,300 --> 00:21:01,470
Для того чтобы найти максимальный подмассива, который заканчивается в позиции I,

287
00:21:01,470 --> 00:21:03,980
У меня есть два варианта: я могу либо продолжить подмассива

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

289
00:21:09,790 --> 00:21:14,190
Если бы я был продолжить подмассива, который начался в предыдущий индекс,

290
00:21:14,190 --> 00:21:19,260
Затем максимальную сумму я могу достичь, это ответ на предыдущий подзадачи

291
00:21:19,260 --> 00:21:24,120
плюс текущий элемент массива.

292
00:21:24,120 --> 00:21:27,550
Но, у меня есть выбор, начиная новый подмассива,

293
00:21:27,550 --> 00:21:30,830
В этом случае сумма равна 0.

294
00:21:30,830 --> 00:21:42,860
Так что ответ макс 0, подзадача - 1, а также текущий элемент массива.

295
00:21:42,860 --> 00:21:46,150
Означает ли это повторение смысла?

296
00:21:46,150 --> 00:21:50,840
Наши рецидива, как мы только что обнаружили, это я подзадача

297
00:21:50,840 --> 00:21:54,740
равен максимуму предыдущего подзадачи плюс мой текущий элемент массива,

298
00:21:54,740 --> 00:22:01,490
что означает продолжение предыдущей подмассива,

299
00:22:01,490 --> 00:22:07,250
или 0, создать новую подмассива на мой текущий индекс.

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

301
00:22:10,060 --> 00:22:13,950
просто делать линейные развертки через подзадачи массива

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
Таким образом, мы создаем новый массив подзадачи, подзадачи.

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

306
00:22:32,330 --> 00:22:35,670
А для остальных подзадач

307
00:22:35,670 --> 00:22:39,810
мы используем точное повторение Мы только что обнаружили.

308
00:22:39,810 --> 00:22:49,960
Теперь вычислим максимальную нашего массива подзадач, и это наш окончательный ответ.

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
Ну, одно следует отметить, что я назвал таНос здесь с размером п.

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
мы заботимся только о предыдущей подзадачи,

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
Последний номер подзадачи массива, а последний номер максимума.

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
Данной суммы до сих пор, здесь заменяет роль подзадачи, наши подзадачи массива.

327
00:24:15,830 --> 00:24:20,020
Таким образом, текущая сумма, до сих пор, является ответом на предыдущий подзадачи.

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
и мы также имеем линейное решение наших подмассива проблемы.

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
"Учитывая массив целых чисел п, положительной, нулевой или отрицательной,

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
при условии, что вы покупаете и продаете ровно 1 акция в рамках этих п дней ".

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), потому что существует п выбрать две пары -

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
Я собираюсь рассказать вам, что есть п § п решение.

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
Найти лучший прибыли вы можете сделать, только с первой русской течение двух дней.

380
00:28:16,480 --> 00:28:19,780
Затем вы хотите oompute лучшие покупки / продажи пары на правой половине,

381
00:28:19,780 --> 00:28:23,930
так что последние п течение двух дней.

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
Если мы определили функцию T (N), что число шагов

419
00:31:41,340 --> 00:31:50,010
для п дней,

420
00:31:50,010 --> 00:31:54,350
наши рекурсивные вызовы

421
00:31:54,350 --> 00:32:00,460
каждый будет стоить т (п / 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
который я могу сделать в п / 2, плюс максимум в правой половине.

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

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
Таким образом, наш алгоритм также п § п времени.

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
Т (п) является ряд шагов, чтобы вычислить максимальную прибыль

434
00:32:59,170 --> 00:33:02,750
в течение суток с.

435
00:33:02,750 --> 00:33:06,010
То, как мы разделились наши рекурсивные вызовы

436
00:33:06,010 --> 00:33:11,980
является вызовом нашего решения в первые дни п / 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
Таким образом, п / 2 + п / 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
Таким образом, наш алгоритм перемешивания также п п войти.

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
порядка журнала N кадров стека.

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 (журнал N) пространства

467
00:35:49,240 --> 00:36:03,040
где п-количество дней.

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
Мы можем преобразовать эту проблему фондового рынка в максимальной проблемы подмассива.

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
(Emmy, непонятные)

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

476
00:36:53,860 --> 00:36:59,940
Таким образом, максимальная подмассива проблемы,

477
00:36:59,940 --> 00:37:10,610
Мы ищем сумма по непрерывной подмассива.

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
Но давайте посмотрим на непрерывное - давайте посмотрим на подмассива проблемы.

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
Ключ к снижению нашем складе проблемой в нашей максимальной проблемы подмассива

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), и массив (я - 1).

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

497
00:38:55,530 --> 00:39:01,500
проходящей в массиве дельты.

498
00:39:01,500 --> 00:39:06,440
И потому, что максимальная подмассива является линейным временем,

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 (п) плюс работа O (п) работы, по-прежнему O (п) работы.

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]