Programmation dynamiqueIntermediate
Algorithme de Kadane (Sous-tableau maximum)
Algorithme élégant de programmation dynamique qui trouve le sous-tableau contigu avec la somme maximale en temps O(n). Combine les principes gloutons et de PD en décidant à chaque étape s'il faut étendre le sous-tableau actuel ou en commencer un nouveau. Essentiel pour l'optimisation des profits boursiers, le traitement du signal et la compréhension des techniques d'optimisation PD.
#dynamic-programming#greedy#optimization#stock-market
Complexity Analysis
Time (Average)
O(n)Expected case performance
Space
O(1)Memory requirements
Time (Best)
O(n)Best case performance
Time (Worst)
O(n)Worst case performance
Step: 1 / 0
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← → StepR Reset1-4 Speed
Real-time Statistics
Algorithm Performance Metrics
Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
Steps
1/ 0
Algorithm Visualization
Step 1 of 0
Initialize array to begin
Default
Comparing
Swapped
Sorted
Code Execution
Currently executing
Previously executed
Implementation