← Back to Home
ក្បួនដោះស្រាយរបស់ Kadane
ក្បួនដោះស្រាយប្រកបដោយប្រសិទ្ធភាពដើម្បីស្វែងរកអារេរងជាប់គ្នាក្នុងអារេមួយវិមាត្រនៃលេខដែលមានផលបូកធំបំផុត។
Visualization
Step 1 / 11
Speed:
Details
Analogy
គិតអំពីការវិភាគការផ្លាស់ប្តូរតម្លៃហ៊ុនប្រចាំថ្ងៃដើម្បីរកពេលវេលាដែលមានប្រាក់ចំណេញច្រើនបំផុត។ អ្នកតាមដានប្រាក់ចំណេញនៃ 'ការជួញដូរ' បច្ចុប្បន្នរបស់អ្នក។ ប្រសិនបើប្រាក់ចំណេញធ្លាក់ចុះក្រោមសូន្យ អ្នក 'លក់' ហើយចាប់ផ្តើមការជួញដូរថ្មីនៅថ្ងៃបន្ទាប់ ដោយសារការកាន់កាប់បន្តនឹងធ្វើឱ្យប្រាក់ចំណេញរបស់អ្នកធ្លាក់ចុះប៉ុណ្ណោះ។ អ្នកតែងតែចងចាំការជួញដូរដែលមានប្រាក់ចំណេញច្រើនបំផុតតែមួយដែលអ្នកបានឃើញ។
Purpose
ដើម្បីដោះស្រាយបញ្ហាអារេរងអតិបរមាក្នុងពេលវេលាលីនេអ៊ែរ។
Use Cases
ប្រើក្នុងការវិភាគទិន្នន័យ ការវិភាគហិរញ្ញវត្ថុ (ឧទាហរណ៍ ការរកពេលវេលានៃប្រាក់ចំណេញអតិបរមាពីតម្លៃហ៊ុន) និង computer vision (ឧទាហរណ៍ ការដំណើរការរូបភាព)។
Algorithm Steps
Line 1
1
maxSoFar = -infinity
2
maxEndingHere = 0
3
for each element x in arr:
4
maxEndingHere = maxEndingHere + x
5
if maxSoFar < maxEndingHere:
6
maxSoFar = maxEndingHere
7
if maxEndingHere < 0:
8
maxEndingHere = 0
9
return maxSoFar
Current
Executed
Pending
Explanation
What's Happening?
Step 1/11
ចាប់ផ្តើម។ Max so far = -∞, Current max = 0។
Updates with each step • Clickfor full view
Code Implementation
def max_sub_array_sum(arr):
max_so_far = -float('inf')
max_ending_here = 0
for x in arr:
max_ending_here = max_ending_here + x
if max_so_far < max_ending_here:
max_so_far = max_ending_here
if max_ending_here < 0:
max_ending_here = 0
return max_so_far