در این مطلب، ویدئو Maximum Subarray – سوال مصاحبه کدنویسی آمازون – Leetcode 53 – Python با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:08:03
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,060 –> 00:00:03,149
اجازه دهید همه ماکزیمم زیر آرایه کد 53 را نشت
2
00:00:03,149 –> 00:00:05,100
کنیم، بنابراین یک آرایه صحیح از
3
00:00:05,100 –> 00:00:06,420
گنوم ها به ما داده می شود و می خواهیم
4
00:00:06,420 –> 00:00:09,179
آرایه فرعی پیوسته حاوی حداقل
5
00:00:09,179 –> 00:00:11,730
یک عدد را پیدا کنیم که دارای بیشترین مجموع باشد و
6
00:00:11,730 –> 00:00:14,130
سپس می خواهیم فقط مجموع را برگردانیم، بنابراین
7
00:00:14,130 –> 00:00:16,139
این آرایه دارای اعداد مثبت
8
00:00:16,139 –> 00:00:18,539
و دارای اعداد منفی است، بنابراین این چیزی است
9
00:00:18,539 –> 00:00:20,880
که باید در نظر داشته باشیم در این مورد
10
00:00:20,880 –> 00:00:23,100
بزرگترین مجموع 6 است و این فقط این
11
00:00:23,100 –> 00:00:25,710
بخش وسط آرایه است، بنابراین اولین
12
00:00:25,710 –> 00:00:27,810
چیزی که ممکن است امتحان کنید این است که
13
00:00:27,810 –> 00:00:30,990
هر آرایه فرعی را درست محاسبه کنید. بنابراین بیایید
14
00:00:30,990 –> 00:00:32,940
ابتدا هر زیرآرایه را
15
00:00:32,940 –> 00:00:35,430
که از منفی 2 شروع می شود محاسبه کنیم، یک
16
00:00:35,430 –> 00:00:38,670
آرایه فرعی وجود دارد، 2 آرایه فرعی وجود دارد، 3 زیرآرایه وجود دارد
17
00:00:38,670 –> 00:00:40,320
و سپس این کار را ادامه می دهیم تا
18
00:00:40,320 –> 00:00:42,450
به انتهای درست برسیم و سپس
19
00:00:42,450 –> 00:00:44,190
می توانیم این روند را برای عدد دوم تکرار کنیم
20
00:00:44,190 –> 00:00:45,989
تا زیر آرایه آرایه ای که از 1 شروع می شود در
21
00:00:45,989 –> 00:00:48,480
اینجا آرایه فرعی دیگری که از 1 شروع می شود در
22
00:00:48,480 –> 00:00:50,760
اینجا آرایه فرعی دیگری که از 1 شروع
23
00:00:50,760 –> 00:00:53,010
می شود تا انتها،
24
00:00:53,010 –> 00:00:54,870
اکنون می توانیم همان روند را
25
00:00:54,870 –> 00:00:57,690
برای هر عدد در آرایه تکرار کنیم، بنابراین بیایید
26
00:00:57,690 –> 00:00:59,370
فقط کد شبه را بنویسیم. e برای اینکه ببینیم
27
00:00:59,370 –> 00:01:01,379
این چه نوع پیچیدگی به همراه خواهد
28
00:01:01,379 –> 00:01:04,199
داشت، بنابراین بیایید بگوییم که ما شروع می کنیم،
29
00:01:04,199 –> 00:01:05,610
چشم مقدار شروع
30
00:01:05,610 –> 00:01:07,229
را نشان می دهد، یعنی
31
00:01:07,229 –> 00:01:09,180
از صفر تا آخرین عدد
32
00:01:09,180 –> 00:01:12,540
n منهای 1 یا آخرین شاخص متغیر است و منهای 1
33
00:01:12,540 –> 00:01:15,720
و سپس می خواهیم شاخص پایانی را بدست آوریم،
34
00:01:15,720 –> 00:01:18,000
بنابراین من از J برای انتهای
35
00:01:18,000 –> 00:01:20,670
این آرایه فرعی استفاده می کنم، بنابراین از I شروع
36
00:01:20,670 –> 00:01:23,100
می کنیم و تا
37
00:01:23,100 –> 00:01:26,280
پایان آرایه فرعی ادامه می دهیم یا تا
38
00:01:26,280 –> 00:01:28,890
پایان کل آرایه و منهای 1، بنابراین این
39
00:01:28,890 –> 00:01:31,020
نشان دهنده شروع است، من
40
00:01:31,020 –> 00:01:33,240
نشان دهنده شروع است.
41
00:01:33,240 –> 00:01:36,390
42
00:01:36,390 –> 00:01:37,920
43
00:01:37,920 –> 00:01:41,100
44
00:01:41,100 –> 00:01:44,189
از I تا J
45
00:01:44,189 –> 00:01:46,110
درست است، زیرا این همان چیزی است که
46
00:01:46,110 –> 00:01:48,270
آرایه فرعی را نشان می دهد و سپس در اینجا ما همین الان مجموع را محاسبه می کنیم
47
00:01:48,270 –> 00:01:52,770
، بدیهی است که این
48
00:01:52,770 –> 00:01:55,110
واقعاً ناکارآمد است درست است،
49
00:01:55,110 –> 00:01:57,600
پیچیدگی زمانی n مکعب است، واضح است
50
00:01:57,600 –> 00:02:00,329
زیرا ما 3 حلقه برای داریم. پس بیایید سعی کنیم این موضوع
51
00:02:00,329 –> 00:02:02,159
را گسترش دهیم، ببینیم آیا می توانیم
52
00:02:02,159 –> 00:02:04,290
m از میانبرهایی برای بهبود آن استفاده کنید، بنابراین
53
00:02:04,290 –> 00:02:05,729
واضح ترین چیزی که احتمالا متوجه خواهید شد این
54
00:02:05,729 –> 00:02:08,699
است که می توانیم در زمان
55
00:02:08,699 –> 00:02:10,500
محاسبه یک زیر آرایه در زمان صرفه جویی کنیم، بنابراین اگر
56
00:02:10,500 –> 00:02:12,940
فرض کنیم این زیر آرایه را درست
57
00:02:12,940 –> 00:02:14,890
محاسبه کرده ایم و می خواهیم زیر آرایه بعدی را محاسبه کنیم.
58
00:02:14,890 –> 00:02:17,050
فقط یک عنصر اضافه شده بود خوب ما می توانیم
59
00:02:17,050 –> 00:02:19,870
نتیجه این حق را ذخیره کنیم و
60
00:02:19,870 –> 00:02:21,580
بگوییم تابستان فعلی ما یا هر چیز دیگری است و
61
00:02:21,580 –> 00:02:24,250
سپس برای محاسبه این آرایه فرعی فقط
62
00:02:24,250 –> 00:02:26,410
باید این عدد را در اینجا اضافه
63
00:02:26,410 –> 00:02:30,010
کنیم تا بتوانیم فقط بگوییم مجموع فعلی به
64
00:02:30,010 –> 00:02:33,100
اضافه 1 و بنابراین این می تواند در زمان ما صرفه جویی کند،
65
00:02:33,100 –> 00:02:34,990
بیایید به پیچیدگی زمانی
66
00:02:34,990 –> 00:02:36,790
این راه حل نگاهی بیندازیم، بنابراین
67
00:02:36,790 –> 00:02:38,530
حلقه for دیگری خواهیم
68
00:02:38,530 –> 00:02:40,750
داشت که شروع را نشان می دهد، بنابراین start
69
00:02:40,750 –> 00:02:43,630
از 0 تا n منهای 1 متغیر است
70
00:02:43,630 –> 00:02:46,300
و ما یک حلقه دیگر
71
00:02:46,300 –> 00:02:48,100
برای انتهای زیر آرایه
72
00:02:48,100 –> 00:02:51,910
خواهیم داشت که J از I 2 آخرین
73
00:02:51,910 –> 00:02:54,940
شاخص n منهای 1 متغیر است و سپس در داخل
74
00:02:54,940 –> 00:02:56,590
حلقه، جمع فعلی خود را حفظ می کنیم
75
00:02:56,590 –> 00:03:01,500
و فقط کافی است عدد J را اضافه کنیم.
76
00:03:01,500 –> 00:03:04,900
هر تکرار حلقه سمت راست، بنابراین
77
00:03:04,900 –> 00:03:06,730
این مقدار کمی ef بیشتر است ضریب o از
78
00:03:06,730 –> 00:03:09,370
مجذور N یک بهینه سازی بسیار آسان است
79
00:03:09,370 –> 00:03:11,440
و راه حل شما را بسیار بهبود می بخشد،
80
00:03:11,440 –> 00:03:13,690
اما آیا می توانیم حتی بهتر از این کار کنیم،
81
00:03:13,690 –> 00:03:15,700
بنابراین اکنون سوالی که باید از
82
00:03:15,700 –> 00:03:18,489
خود بپرسید این است که آیا ما باید هر
83
00:03:18,489 –> 00:03:21,730
زیر آرایه را با هر مقدار شروع
84
00:03:21,730 –> 00:03:23,290
کنیم. آرایه درست است آیا باید از
85
00:03:23,290 –> 00:03:26,470
هر مقدار شروع کنیم و هر
86
00:03:26,470 –> 00:03:28,660
آرایه فرعی که بعد از آن می آید را محاسبه
87
00:03:28,660 –> 00:03:30,910
کنیم، فکر نمی کنم به یاد داشته باشیم که در حال تلاش برای
88
00:03:30,910 –> 00:03:33,760
یافتن حداکثر آرایه فرعی هستیم که می توانیم از
89
00:03:33,760 –> 00:03:36,970
آن دانش برای کمک به ایجاد
90
00:03:36,970 –> 00:03:39,760
میانبر استفاده کنیم. پس بیایید نگاهی به این بیندازیم
91
00:03:39,760 –> 00:03:42,160
، ما یک منفی 2 داریم، بنابراین وقتی
92
00:03:42,160 –> 00:03:43,900
از اینجا شروع می کنیم، حداکثر
93
00:03:43,900 –> 00:03:47,800
مجموع ما تا اینجای کار خواهد بود، سپس به منفی 2
94
00:03:47,800 –> 00:03:51,400
به اضافه 1 می رسیم، بنابراین این منفی 1 است تا اینجا به
95
00:03:51,400 –> 00:03:54,430
راست است، آیا واقعاً به این منفی نیاز داریم
96
00:03:54,430 –> 00:03:56,530
عدد، اعداد منفی
97
00:03:56,530 –> 00:03:58,930
در این مورد هیچ کمکی ندارند، درست است،
98
00:03:58,930 –> 00:04:02,260
بنابراین میتوانیم دیسک کنیم و اساساً میتوانیم
99
00:04:02,260 –> 00:04:05,709
آن مقدار را درست زمانی که به اینجا