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だし、私は私が下級生だったとき、私はこれを持って望む

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ドキュメントのどちらかはそう彼らはあなたが見ることができるライブコーディング

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
"n個の整数の配列を指定して、配列をシャッフルする関数を書く

77
00:04:14,790 --> 00:04:20,209
n個の整数のすべての順列が等しく可能性があるとそのような場所で "を意味する。

78
00:04:20,209 --> 00:04:23,470
とは、利用可能な整数の乱数発生器を持っていると仮定

79
00:04:23,470 --> 00:04:30,980
それは半分の範囲は、0からiの範囲の整数を生成します。

80
00:04:30,980 --> 00:04:32,970
誰もがこの問題を理解していますか？

81
00:04:32,970 --> 00:04:39,660
私はあなたにn個の整数の配列を与える、と私はあなたがそれをシャッフルしたい。

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
オーケー。エミーによって示唆だから1アイデア、

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
そして私は、randによって返されたに基づいて - 

100
00:06:12,880 --> 00:06:17,580
私がいたので、もし、17日としましょう

101
00:06:17,580 --> 00:06:25,640
最初の位置に第十七要素をコピーします。

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
我々はここで新しいiを持って、私たちはこの位置に、この要素をコピーします。

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
我々はこのiを削除するとき、我々は左にそれの後にすべての要素をシフトしている。

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（n）操作が発生

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
またはフィッシャーYatesのシャッフル。

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
その代わりに私たちの入力/出力の2つの配列を使用しての、

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
それで、我々の新しいiがここにあると仮定します。

139
00:09:30,650 --> 00:09:39,370
今、私たちはここで私たちの現在の新しい位置でこのiを入れ替える。

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部分で、iは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
>> まあ、1が質問を必要とされ、なぜこれは正しいのですか？

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
オーケー。クール。

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
私のshuffleはすべての順列同じ確率を返します

158
00:10:53,290 --> 00:10:56,120
まで最初のi個の要素に。

159
00:10:56,120 --> 00:10:58,300
さて、I + 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
だから "、負、ゼロ、ポジティブ整数の配列を、与えられた

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
この場合、我々は最初の2つだけにしたい

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
次に、いずれかの私は1,000〜20,000を選択

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
>> に我々の強引な解決策、start / endインデックスを使用する場合

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
と>または=を開始するすべてのエンドエントリ用、および<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
時間的に。

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
その結果は、forループの一つだ。

212
00:14:27,520 --> 00:14:35,120
我々は、別のforループでは、ほとんど最初から最後まで、もう一度反復する。

213
00:14:35,120 --> 00:14:37,640
そして今、その中で、我々は、すべてのエントリを総括しなければならない

214
00:14:37,640 --> 00:14:43,810
その結果、ループのための別のです。だから我々は3つのネストされたforループは、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
開始と終了：これはで私が何を意味するか、我々は現在、2つのことを心配する必要があります。

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
範囲内の任意の部分配列[O、N-1]の最大合計数を見つける。

226
00:15:37,470 --> 00:15:47,400
そして今、我々は、我々の現在のインデックスiに、私たちが知っている新しいサブ問題を、持っている

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
[学生]ゼロ。 >>ゼロ。ちょうど-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はどこにいるのか？ゼロ。

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、および最後の1は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
だからここに、8 0、0、0、1、5であった。

272
00:19:35,930 --> 00:19:39,790
そしてそこここに-2であった、そしてそれは6にダウンしました。

273
00:19:39,790 --> 00:19:50,800
だから私は、位置iのサブ問題（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
[ゆう]だか​​ら彼女の提案は、これら2つの数字を見ることである、

283
00:20:36,460 --> 00:20:40,090
この番号とこの番号。

284
00:20:40,090 --> 00:20:50,130
だから、この8は部分問題の答え（1  -  i）を指す。

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
私は2つの選択肢があります：私はどちらかのサブアレイを続けることができます

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
1に加えて、現在の配列エントリ - だから答えは0の最大値、サブ問題iである。

295
00:21:42,860 --> 00:21:46,150
この再発は理にかなっていますか？

296
00:21:46,150 --> 00:21:50,840
当社の再発は、我々がちょうど発見したように、サブ問題iである

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または最初のエントリは、それらの2の最大のいずれかです。

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
さて、もう一つ注意すべきは、私は、サイズnと一緒にここにmalloc関数と呼ばれることです。

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
我々は唯一の最後の番号は、最後の2つの数字が必要です。

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
"正、ゼロ、または負のn個の整数の配列を指定して、

348
00:25:38,350 --> 00:25:41,680
N日間の株価を表す、

349
00:25:41,680 --> 00:25:44,080
あなたが作るこ​​とができる最大の利益を計算する関数を書く

350
00:25:44,080 --> 00:25:49,350
あなたはこれらのn日以内に正確に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
私が独自に私が作る利益を決定する必要があります2つのことは何ですか？右。

362
00:26:53,150 --> 00:26:59,410
強引なソリューションです - ああ、そう、ジョージの提案は、我々は唯一の二日必要です

363
00:26:59,410 --> 00:27:02,880
ユニークな2日間の利益を決定する。

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の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
私はnログn解決策があることを伝えるつもりです。

372
00:27:37,420 --> 00:27:45,550
あなたは現在、nログnであるものは何なアルゴリズムを知っていますか？

373
00:27:45,550 --> 00:27:50,730
それはトリックの質問ではありません。

374
00:27:50,730 --> 00:27:54,790
>> マージソート。マージソートは、nログnです

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
あなたはわずか2日間の最初のn個で、作ることができる最善の利益を見つける。

380
00:28:16,480 --> 00:28:19,780
その後は、ベストバイをoompute /右半分にペアを販売したい

381
00:28:19,780 --> 00:28:23,930
2日間のため最後の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
我々は、これらの2つの数値を比較した場合しかし、我々は事件を逃している

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
売る/買うペアはここでしか発生したので、2例、

397
00:29:50,850 --> 00:30:01,910
ここだけ、または両方の半分で、これらの3つの番号で定義されます。

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
結果として3利益は、これらの3つの数字は、あなたは、最大3つを取る

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
これら二つのforループは、それぞれ左と右半分の最小値と最大値を計算します。

409
00:30:50,720 --> 00:30:54,970
今、私は両方の半分にまたがる利益を計算し、

410
00:30:54,970 --> 00:31:00,530
そして最終的な答えは、これらの3つの最大値です。

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
2にしてから再び一緒に当社のソリューションをマージ

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
n日のために、

420
00:31:50,010 --> 00:31:54,350
私たちの2つの再帰呼び出し

421
00:31:54,350 --> 00:32:00,460
各々はT（N / 2）、費用としている

422
00:32:00,460 --> 00:32:03,540
そして、これらの呼び出しの2があります。

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
そして、我々はすべてのマージソート、常にn log n時間であることを知っている。

430
00:32:39,170 --> 00:32:46,880
したがって、我々のアルゴリズムは、nログ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
その結果は、1つのコールだが、

438
00:33:14,490 --> 00:33:16,940
それから私達は後半に再び呼び出す。

439
00:33:16,940 --> 00:33:20,440
だから、2つの呼び出しです。

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のちょうどnです。

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は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
最初の4つのエントリにシャッフルを呼び出すとなる、

454
00:34:41,580 --> 00:34:46,250
これは、最初の2つのエントリでシャッフルを呼び出します。

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（log n）の空間です

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
私たちは最大の部分配列の問題に、この株式市場の問題に変換することができます。

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
だから、最大の部分配列の問題、

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）、および配列（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（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]