در این مطلب، ویدئو حداکثر مجموع زیرآرایه یک آرایه را در پایتون پیدا کنید با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:11:28
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:04,100 –> 00:00:07,520
[موسیقی] فرض کنید
2
00:00:07,520 –> 00:00:08,960
به ما آرایه ای از
3
00:00:08,960 –> 00:00:11,040
اعداد صحیح داده شده است و می خواهیم حداکثر
4
00:00:11,040 –> 00:00:11,440
مجموع را
5
00:00:11,440 –> 00:00:14,400
در یک زیرآرایه غیر خالی به هم پیوسته پیدا کنیم، به
6
00:00:14,400 –> 00:00:16,000
عنوان مثال اگر من این لیست را
7
00:00:16,000 –> 00:00:16,480
در اینجا
8
00:00:16,480 –> 00:00:18,080
با هشت عنصر متشکل از
9
00:00:18,080 –> 00:00:20,320
منفی یک سه منفی دو
10
00:00:20,320 –> 00:00:23,279
پنج سه داشته باشم. منفی پنج دو و دو
11
00:00:23,279 –> 00:00:25,039
سپس میخواهم حداکثر مجموع ممکنی را که میتوانم ایجاد کنم پیدا کنم،
12
00:00:25,039 –> 00:00:26,480
13
00:00:26,480 –> 00:00:28,240
با توجه به اینکه هر زیرآرایهای دلخواه به
14
00:00:28,240 –> 00:00:30,320
هم پیوسته غیر خالی را انتخاب میکنم
15
00:00:30,320 –> 00:00:33,280
، به عنوان مثال اگر آرایه فرعی را
16
00:00:33,280 –> 00:00:33,760
از
17
00:00:33,760 –> 00:00:36,399
منفی پنج به دو انتخاب کنم که این
18
00:00:36,399 –> 00:00:37,360
سه عنصر را پوشش میدهد،
19
00:00:37,360 –> 00:00:39,760
آنگاه ممکن است مجموع در اینجا
20
00:00:39,760 –> 00:00:41,280
منفی یک خواهد بود زیرا منفی پنج بعلاوه
21
00:00:41,280 –> 00:00:42,320
دو منفی سه
22
00:00:42,320 –> 00:00:44,480
به علاوه دو منفی یک است اکنون
23
00:00:44,480 –> 00:00:45,840
نکته این مشکل این است که حداکثر
24
00:00:45,840 –> 00:00:46,640
یک ممکن را پیدا کنیم
25
00:00:46,640 –> 00:00:48,000
و معلوم می شود که حداکثر
26
00:00:48,000 –> 00:00:49,680
مجموع ممکن 9 است
27
00:00:49,680 –> 00:00:52,879
و می توانیم با گرفتن آن را ایجاد کنیم. این
28
00:00:52,879 –> 00:00:55,120
عناصر دقیقاً در اینجا، بنابراین ما سه
29
00:00:55,120 –> 00:00:55,920
منفی دو
30
00:00:55,920 –> 00:00:58,559
پنج و سه داریم و مجموع آنها 9 میشود. پس
31
00:00:58,559 –> 00:01:00,239
چگونه میتوانیم این را به خوبی حل
32
00:01:00,239 –> 00:01:02,719
کنیم، ما دو مرحله را دنبال
33
00:01:02,719 –> 00:01:04,959
میکنیم، بنابراین اولین قدم ما نسلها است. یک آرایه جمع پیشوندی داشته باشید
34
00:01:04,959 –> 00:01:06,880
و من فقط آن را
35
00:01:06,880 –> 00:01:08,240
به عنوان psa مخفف کردم
36
00:01:08,240 –> 00:01:09,760
و سپس گام دوم ما پس از
37
00:01:09,760 –> 00:01:11,600
انجام این کار، یافتن بزرگترین
38
00:01:11,600 –> 00:01:12,000
تفاوت
39
00:01:12,000 –> 00:01:14,400
بین دو مجموع در آرایه مجموع پیشوند است،
40
00:01:14,400 –> 00:01:15,600
بنابراین دلیل ایجاد آن
41
00:01:15,600 –> 00:01:17,600
مجموع پیشوند یا نرخ در وهله اول این
42
00:01:17,600 –> 00:01:20,000
است که ما باید در واقع
43
00:01:20,000 –> 00:01:21,280
مجموع بین
44
00:01:21,280 –> 00:01:23,360
دو محدوده مختلف را پیدا کنیم، زیرا این باید به
45
00:01:23,360 –> 00:01:24,320
هم پیوسته باشد،
46
00:01:24,320 –> 00:01:25,680
بنابراین من همیشه نوعی
47
00:01:25,680 –> 00:01:27,600
کران پایین و برخی کران بالایی دارم
48
00:01:27,600 –> 00:01:30,240
و مقداری از مراحل خطی طول می کشد تا
49
00:01:30,240 –> 00:01:31,600
در واقع
50
00:01:31,600 –> 00:01:34,000
هر مجموع را با دست محاسبه کنیم، بنابراین اگر از قبل
51
00:01:34,000 –> 00:01:36,079
آن را محاسبه کنیم، اگر زمانی نیاز به محاسبه
52
00:01:36,079 –> 00:01:38,479
مجموع داشتیم، میتوانیم به سادگی این کار را با
53
00:01:38,479 –> 00:01:40,880
ارجاع به کران پایین و کران بالا انجام دهیم و
54
00:01:40,880 –> 00:01:42,000
من یک ویدیوی گذشته
55
00:01:42,000 –> 00:01:44,320
در مورد اصول اولیه جمعهای پیشوندی ایجاد کردهام. از طریق
56
00:01:44,320 –> 00:01:46,000
جستارهای مجموع محدوده، می توانید آن
57
00:01:46,000 –> 00:01:46,320
را
58
00:01:46,320 –> 00:01:48,640
در کانال یوتیوب من بررسی کنید، بنابراین ما از این
59
00:01:48,640 –> 00:01:50,240
مفهوم خلاصه پیشوند در مرحله اول استفاده خواهیم کرد
60
00:01:50,240 –> 00:01:51,439
و سپس مرحله دوم
61
00:01:51,439 –> 00:01:53,520
مهم است، زیرا برای یافتن
62
00:01:53,520 –> 00:01:55,600
این حداکثر باید حداکثر تفاوت
63
00:01:55,600 –> 00:01:56,240
ممکن را پیدا کنیم.
64
00:01:56,240 –> 00:01:58,320
کران بالا
65
00:01:58,320 –> 00:02:00,079
و کران پایین و بنابراین این به
66
00:02:00,079 –> 00:02:01,280
ما کمک میکند تا آن را پیدا کنیم،
67
00:02:01,280 –> 00:02:02,799
بنابراین بیایید با اولین مرحله شروع کنیم،
68
00:02:02,799 –> 00:02:04,399
فرض کنید من آرایه جمع پیشوند خود را ایجاد
69
00:02:04,399 –> 00:02:07,200
میکنم و فقط آن را sums مینامم،
70
00:02:07,200 –> 00:02:08,000
بنابراین میگوییم
71
00:02:08,000 –> 00:02:11,280
که مجموع است
72
00:02:11,280 –> 00:02:13,280
برابر است با برخی از لیست ها و بیایید شروع به پر کردن
73
00:02:13,280 –> 00:02:14,959
آن کنیم، بنابراین ما
74
00:02:14,959 –> 00:02:16,959
فقط یک صفر را در ابتدا وارد می کنیم، بنابراین
75
00:02:16,959 –> 00:02:17,680
76
00:02:17,680 –> 00:02:19,440
نشان دهنده این است که ما هنوز
77
00:02:19,440 –> 00:02:21,120
از هیچ عنصری استفاده نمی کنیم
78
00:02:21,120 –> 00:02:23,280
و اکنون عنصر بعدی اولین عنصر را
79
00:02:23,280 –> 00:02:24,480
اضافه می کند.
80
00:02:24,480 –> 00:02:26,640
پس صفر را به منفی یک اضافه می کنیم و بعد
81
00:02:26,640 –> 00:02:28,160
به ما یک منفی
82
00:02:28,160 –> 00:02:30,800
می دهیم، سه را اضافه می کنیم، پس سه دو منفی
83
00:02:30,800 –> 00:02:32,400
یک به ما دو می دهد
84
00:02:32,400 –> 00:02:34,720
بنابراین در اینجا دو داریم و سپس یک
85
00:02:34,720 –> 00:02:36,720
منفی دو اضافه می کنیم تا به صفر برگردیم
86
00:02:36,720 –> 00:02:39,120
و سپس پنج را اضافه می کنیم. به پنج
87
00:02:39,120 –> 00:02:40,239
میرویم و سپس سه را اضافه
88
00:02:40,239 –> 00:02:43,040
میکنیم تا به هشت افزایش میدهیم و سپس
89
00:02:43,040 –> 00:02:45,680
پنج را کم میکنیم تا به سه برگردیم
90
00:02:45,680 –> 00:02:47,840
و سپس دو افزایش میدهیم بنابراین به
91
00:02:47,840 –> 00:02:48,959
پنج
92
00:02:48,959 –> 00:02:50,800
میرویم و در نهایت دوباره 2 افزایش میدهیم و
93
00:02:50,800 –> 00:02:52,560
به 7 میرویم
94
00:02:52,560 –> 00:02:54,959
و بنابراین ما در نهایت با یک لیست مبالغی روبرو
95
00:02:54,959 –> 00:02:56,480
می شویم که چیزی شبیه به این است
96
00:02:56,480 –> 00:02:58,480
تا اولین مورد ما را پوشش دهد اکنون
97
00:02:58,480 –> 00:03:00,080
باید مرحله دوم خود را انجام دهیم،
98
00:03:00,080 –> 00:03:01,680
بنابراین با توجه به اینکه این لیست را داریم،
99
00:03:01,680 –> 00:03:03,440
باید بزرگترین تفاوت بین
100
00:03:03,440 –> 00:03:04,400
دو مجموع را
101
00:03:04,400 –> 00:03:06,239
در آرایه مبالغ پیدا کنیم، بنابراین چگونه می خواهیم این کار را
102
00:03:06,239 –> 00:03:07,760
به خوبی انجام دهیم، یکی از راه های انجام
103
00:03:07,760 –> 00:03:09,120
این کار ممکن است این باشد که
104
00:03:09,120 –> 00:03:11,200
فقط یک brute force تودرتو انجام دهید تا
105
00:03:11,200 –> 00:03:12,640
اساساً به این معنی باشد که من
106
00:03:12,640 –> 00:03:14,560
یک بار در کل لیست خود را جستجو می کنم
107
00:03:14,560 –> 00:03:16,239
و برای هر یک از آن
108
00:03:16,239 –> 00:03:18,319
جستجوها دوباره در لیست جستجو می کنم برای
109
00:03:18,319 –> 00:03:20,080
هر شاخص بعد از آن شاخصی که از آن شروع می کنم
110
00:03:20,080 –> 00:03:20,800
111
00:03:20,800 –> 00:03:22,640
و می توانیم این کار را انجام دهید اما این
112
00:03:22,640 –> 00:03:24,000
خیلی کند خواهد بود و در واقع
113
00:03:24,000 –> 00:03:24,480
114
00:03:24,480 –> 00:03:26,720
الگوریتم ما را به یک زمان اجرا درجه دوم تبدیل می کند
115
00:03:26,720 –> 00:03:28,560
و ما یک زمان اجرا درجه دوم نمی خواهیم و
116
00:03:28,560 –> 00:03:30,159
می خواهیم ببینیم که آیا می توانیم آن
117
00:03:30,159 –> 00:03:31,200
را کمی کمتر از آن کنیم زیرا
118
00:03:31,200 –> 00:03:33,280
در غیر این صورت خیلی طول میکشد، بنابراین
119
00:03:33,280 –> 00:03:34,879
روش دیگری که میتوانیم استفاده کنیم
120
00:03:34,879 –> 00:03:36,560
این است که به عقب میرود، ما
121
00:03:36,560 –> 00:03:38,400
حداکثر حد بالایی ممکن را
122
00:03:38,400 –> 00:03:40,879
که دیدهایم پیگیری میکنیم و همانطور که به
123
00:03:40,879 –> 00:03:41,760
عقب
124
00:03:41,760 –> 00:03:43,360
میرویم، آن
125
00:03:43,360 –> 00:03:45,040
کران پایین را فاکتور میکنیم. که می بینیم که ماکزیمم بالا را به
126
00:03:45,040 –> 00:03:46,000
روز می کنیم
127
00:03:46,000 –> 00:03:47,760
محدود است که میتوانیم ببینیم و میخواهیم
128
00:03:47,760 –> 00:03:49,920
حداکثر تفاوت ممکنی را
129
00:03:49,920 –> 00:03:51,200
که در
130
00:03:51,200 –> 00:03:53,280
حال حاضر داریم، قبل از نوشتن این موضوع پیدا کنیم،
131
00:03:53,280 –> 00:03:54,560
فقط باید در نظر بگیریم که
132
00:03:54,560 –> 00:03:57,280
آرایه فرعی باید خالی نباشد، بنابراین
133
00:03:57,280 –> 00:03:58,720
هر زمان که
134
00:03:58,720 –> 00:04:00,720
هر نوع را در نظر بگیریم. تفاوت بین
135
00:04:00,720 –> 00:04:01,840
کران بالا و کران پایین باید
136
00:04:01,840 –> 00:04:03,680
اطمینان حاصل کنیم که کران بالا با
137
00:04:03,680 –> 00:04:05,360
شاخص کران پایین برابر نیست زیرا اگر
138
00:04:05,360 –> 00:04:06,879
آنها برابر باشند به این معنی است که ما
139
00:04:06,879 –> 00:04:08,560
سعی کرده ایم یک آرایه فرعی را بگیریم که
140
00:04:08,560 –> 00:04:10,400
خالی است، بنابراین بیایید با i
141
00:04:10,400 –> 00:04:13,360
برابر با هفت شروع کنیم. بنابراین من برابر با هفت و در i
142
00:04:13,360 –> 00:04:14,000
برابر با هفت،
143
00:04:14,000 –> 00:04:15,840
بیایید بگوییم که حداکثر
144
00:04:15,840 –> 00:04:17,120
کران بالایی ممکن که
145
00:04:17,120 –> 00:04:19,519
می بینیم آخرین عنصر
146
00:04:19,519 –> 00:04:20,320
در اینجا خواهد بود،
147
00:04:20,320 –> 00:04:23,120
بنابراین حداکثر انتهای آن چیزی است که ما آن را
148
00:04:23,120 –> 00:04:23,919
149
00:04:23,919 –> 00:04:25,520
حداکثر پایان برابر با هفت می نامیم زیرا توجه کنید که
150
00:04:25,520 –> 00:04:27,120
ما دوباره از یک شاخص قبل از
151
00:04:27,120 –> 00:04:28,800
آخرین شاخص شروع می کنیم که فقط برای اطمینان از اینکه
152
00:04:28,800 –> 00:04:29,440
ما
153
00:04:29,440 –> 00:04:31,840
یک زیرآرایه غیر خالی را حفظ می کنیم، وقتی
154
00:04:31,840 –> 00:04:32,479
این را
155
00:04:32,479 –> 00:04:34,400
داریم، می توانیم آنچه را که فکر می کنیم
156
00:04:34,400 –> 00:04:35,919
در حال حاضر حداکثر مجموع باشد و
157
00:04:35,919 –> 00:04:37,360
آن هفت منهای پنج باشد،
158
00:04:37,360 –> 00:04:39,360
بنابراین این است عنصر منهای این
159
00:04:39,360 –> 00:04:40,400
عنصر
160
00:04:40,400 –> 00:04:42,479
و تفاوت دو است، بنابراین اجازه
161
00:04:42,479 –> 00:04:44,479
دهید مجموع را
162
00:04:44,479 –> 00:04:46,720
برابر با دو صدا کنم خیلی خوب، بیایید به
163
00:04:46,720 –> 00:04:47,600
شاخص شش
164
00:04:47,600 –> 00:04:50,320
برویم، بنابراین من برابر است با شش و در این مرحله اکنون می توانیم
165
00:04:50,320 –> 00:04:51,520
ببینیم که
166
00:04:51,520 –> 00:04:53,360
پنج چاه داریم پنج هنوز کمتر از هفت است
167
00:04:53,360 –> 00:04:55,280
بنابراین حداکثر پایان همچنان هفت خواهد بود
168
00:04:55,280 –> 00:04:58,800
پس حداکثر و
169
00:04:58,800 –> 00:05:01,440
برابر با هفت و مجموع ما
170
00:05:01,440 –> 00:05:01,919
هفت
171
00:05:01,919 –> 00:05:05,440
منهای سه که چهار می شود
172
00:05:05,840 –> 00:05:08,560
بنابراین مجموع برابر با چهار خواهد شد و بنابراین
173
00:05:08,560 –> 00:05:10,479
حداکثر مجموع ما را که در اینجا داریم به روز می کنیم
174
00:05:10,479 –> 00:05:11,120
175
00:05:11,120 –> 00:05:14,000
و اکنون به شاخص پنج می رویم. شاخص
176
00:05:14,000 –> 00:05:15,520
پنج، عنصر هشت را
177
00:05:15,520 –> 00:05:18,160
داریم و میتوانیم حداکثر پایان خود را به صورت سه خوب ببینیم،
178
00:05:18,160 –> 00:05:19,360
سه هنوز کمتر از هفت،
179
00:05:19,360 –> 00:05:22,400
بنابراین ما همچنان حداکثر پایان را
180
00:05:22,400 –> 00:05:25,840
برابر با هفت حفظ
181
00:05:25,919 –> 00:05:28,400
میکنیم و سپس مجموع ما هفت
182
00:05:28,400 –> 00:05:29,440
منهای هشت میشود
183
00:05:29,440 –> 00:05:30,800
اما سپس هفت منهای هشت میشود. منفی
184
00:05:30,800 –> 00:05:32,63