-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path0053_maximum_subarray.html
More file actions
433 lines (359 loc) · 16.2 KB
/
Copy path0053_maximum_subarray.html
File metadata and controls
433 lines (359 loc) · 16.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>LC 53: Maximum Subarray - Algorithm Visualization</title>
<link rel="stylesheet" href="styles.css">
<script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
<div class="container">
<div class="problem-info">
<h1><span class="problem-number">#53</span> Maximum Subarray</h1>
<p>Given an integer array, find the contiguous subarray with the largest sum and return its sum.</p>
<div class="problem-meta">
<span class="meta-tag">🤑 Greedy</span>
<span class="meta-tag">📈 Kadane's Algorithm</span>
<span class="meta-tag">⏱️ O(n)</span>
<span class="meta-tag">💾 O(1)</span>
</div>
<div class="file-ref">
📄 Python: <code>python/0053_maximum_subarray/0053_maximum_subarray.py</code>
</div>
</div>
<div class="explanation-panel">
<h4>🧠 How It Works (Layman's Terms)</h4>
<p>At each position, ask yourself: <strong>"Should I keep adding to my current streak, or start fresh?"</strong></p>
<ul>
<li><strong>curr_sum:</strong> Best sum ending at current position</li>
<li><strong>max_sum:</strong> Best sum seen so far (the answer)</li>
<li><strong>Key insight:</strong> If current sum is negative, it's better to start fresh!</li>
<li><strong>Decision:</strong> max(start fresh, keep going) = max(num, curr_sum + num)</li>
</ul>
</div>
<div class="visualization-section">
<h3>🎬 Step-by-Step Visualization</h3>
<div class="controls">
<button class="btn btn-primary" id="stepBtn" onclick="step()">Step</button>
<button class="btn btn-success" id="autoBtn" onclick="toggleAuto()">Auto Run</button>
<button class="btn btn-warning" onclick="reset()">Reset</button>
</div>
<div class="info-box secondary" style="margin-bottom: 20px;">
📊 Array: <strong>[-2, 1, -3, 4, -1, 2, 1, -5, 4]</strong>
</div>
<div class="status-message" id="statusMessage">
Click "Step" or "Auto Run" to start visualization
</div>
<div class="array-section">
<div class="array-label">📊 Array:</div>
<div class="array-container" id="arrayContainer"></div>
</div>
<div class="variable-section" style="margin: 20px 0; display: flex; gap: 30px; justify-content: center; flex-wrap: wrap;">
<div class="variable" style="background: #e3f2fd;">
<span class="var-name">curr_sum</span>
<span class="var-value" id="currSumValue">-2</span>
<span class="var-desc">best ending here</span>
</div>
<div class="variable" style="background: #e8f5e9;">
<span class="var-name">max_sum</span>
<span class="var-value" id="maxSumValue">-2</span>
<span class="var-desc">overall best</span>
</div>
</div>
<div class="explanation-panel" style="margin-top: 20px;">
<h4>📝 Current Decision</h4>
<div id="decisionDisplay" style="font-size: 1.1em; padding: 10px;">
Waiting to start...
</div>
</div>
<div id="chartContainer" style="width: 100%; height: 200px; margin-top: 20px;"></div>
</div>
<div class="code-section">
<h3>💻 Python Solution (Kadane's Algorithm)</h3>
<div class="code-block">
<pre>from typing import List
"""
LeetCode Maximum Subarray
Problem from LeetCode: https://leetcode.com/problems/maximum-subarray/
Description:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
"""
class Solution:
def max_sub_array(self, nums: List[int]) -> int:
"""
Find the contiguous subarray with the largest sum using Kadane's algorithm.
Args:
nums: Array of integers
Returns:
int: The largest sum of a contiguous subarray
"""
if not nums:
return 0
# Initialize variables to track current sum and maximum sum
curr_sum = max_sum = nums[0]
# Iterate through the array starting from the second element
for num in nums[1:]:
# Either start a new subarray or extend the existing one
curr_sum = max(num, curr_sum + num)
# Update the maximum sum if necessary
max_sum = max(max_sum, curr_sum)
return max_sum
def max_sub_array_divide_conquer(self, nums: List[int]) -> int:
"""
Find the maximum subarray sum using a divide and conquer approach.
Args:
nums: Array of integers
Returns:
int: The largest sum of a contiguous subarray
"""
def find_max_crossing(nums, left, mid, right):
"""Find the maximum sum crossing the middle element."""
# Find maximum subarray sum including the middle element and extending to the left
left_sum = float('-inf')
curr_sum = 0
for i in range(mid, left - 1, -1):
curr_sum += nums[i]
left_sum = max(left_sum, curr_sum)
# Find maximum subarray sum including the middle element and extending to the right
right_sum = float('-inf')
curr_sum = 0
for i in range(mid + 1, right + 1):
curr_sum += nums[i]
right_sum = max(right_sum, curr_sum)
# Return the sum of the two parts
return left_sum + right_sum
def find_max_subarray(nums, left, right):
"""Recursively find the maximum subarray sum."""
# Base case: single element
if left == right:
return nums[left]
# Divide the array
mid = (left + right) // 2
# Find max in left half, right half, and crossing the middle
left_max = find_max_subarray(nums, left, mid)
right_max = find_max_subarray(nums, mid + 1, right)
cross_max = find_max_crossing(nums, left, mid, right)
# Return the maximum of the three
return max(left_max, right_max, cross_max)
return find_max_subarray(nums, 0, len(nums) - 1)
if __name__ == '__main__':
# Example usage based on LeetCode sample
solution = Solution()
# Example 1
nums1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result1 = solution.max_sub_array(nums1)
print(f"Example 1: {result1}") # Expected output: 6
# Example 2
nums2 = [1]
result2 = solution.max_sub_array(nums2)
print(f"Example 2: {result2}") # Expected output: 1
# Example 3
nums3 = [5, 4, -1, 7, 8]
result3 = solution.max_sub_array(nums3)
print(f"Example 3: {result3}") # Expected output: 23
# Compare with divide and conquer approach
print("\nUsing divide and conquer approach:")
print(f"Example 1: {solution.max_sub_array_divide_conquer(nums1)}")
print(f"Example 3: {solution.max_sub_array_divide_conquer(nums3)}")
</pre>
</div>
</div>
</div>
<script>
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
let currSum = nums[0];
let maxSum = nums[0];
let currentIdx = 0;
let subarrayStart = 0;
let bestStart = 0;
let bestEnd = 0;
let autoInterval = null;
let history = [{idx: 0, currSum: nums[0], maxSum: nums[0]}];
function init() {
renderArray();
renderChart();
updateVariables();
}
function renderArray() {
const container = document.getElementById('arrayContainer');
container.innerHTML = '';
nums.forEach((val, i) => {
const box = document.createElement('div');
box.className = 'array-box';
box.id = `num-${i}`;
box.innerHTML = `${val}<span class="index-label">${i}</span>`;
// Color the current subarray
if (i >= subarrayStart && i <= currentIdx) {
box.style.background = '#bbdefb';
box.style.borderColor = '#2196f3';
}
// Highlight best subarray found so far
if (i >= bestStart && i <= bestEnd) {
box.style.background = '#c8e6c9';
box.style.borderColor = '#4caf50';
}
// Current position
if (i === currentIdx) {
box.classList.add('highlight');
}
container.appendChild(box);
});
}
function renderChart() {
d3.select('#chartContainer').selectAll('*').remove();
const margin = {top: 20, right: 30, bottom: 40, left: 50};
const width = document.getElementById('chartContainer').offsetWidth - margin.left - margin.right;
const height = 160 - margin.top - margin.bottom;
const svg = d3.select('#chartContainer')
.append('svg')
.attr('width', width + margin.left + margin.right)
.attr('height', height + margin.top + margin.bottom)
.append('g')
.attr('transform', `translate(${margin.left},${margin.top})`);
const xScale = d3.scaleLinear()
.domain([0, nums.length - 1])
.range([0, width]);
const minVal = Math.min(...history.map(h => Math.min(h.currSum, h.maxSum)), -5);
const maxVal = Math.max(...history.map(h => Math.max(h.currSum, h.maxSum)), 10);
const yScale = d3.scaleLinear()
.domain([minVal - 1, maxVal + 1])
.range([height, 0]);
// Zero line
svg.append('line')
.attr('x1', 0)
.attr('x2', width)
.attr('y1', yScale(0))
.attr('y2', yScale(0))
.attr('stroke', '#999')
.attr('stroke-dasharray', '3,3');
// curr_sum line
const currLine = d3.line()
.x(d => xScale(d.idx))
.y(d => yScale(d.currSum));
svg.append('path')
.datum(history)
.attr('fill', 'none')
.attr('stroke', '#2196f3')
.attr('stroke-width', 2)
.attr('d', currLine);
// max_sum line
const maxLine = d3.line()
.x(d => xScale(d.idx))
.y(d => yScale(d.maxSum));
svg.append('path')
.datum(history)
.attr('fill', 'none')
.attr('stroke', '#4caf50')
.attr('stroke-width', 3)
.attr('d', maxLine);
// Axes
svg.append('g')
.attr('transform', `translate(0,${height})`)
.call(d3.axisBottom(xScale).ticks(nums.length));
svg.append('g')
.call(d3.axisLeft(yScale));
// Legend
svg.append('line').attr('x1', width - 100).attr('y1', 5).attr('x2', width - 80).attr('y2', 5).attr('stroke', '#2196f3').attr('stroke-width', 2);
svg.append('text').attr('x', width - 75).attr('y', 8).text('curr_sum').style('font-size', '11px');
svg.append('line').attr('x1', width - 100).attr('y1', 20).attr('x2', width - 80).attr('y2', 20).attr('stroke', '#4caf50').attr('stroke-width', 3);
svg.append('text').attr('x', width - 75).attr('y', 23).text('max_sum').style('font-size', '11px');
}
function updateVariables() {
document.getElementById('currSumValue').textContent = currSum;
document.getElementById('maxSumValue').textContent = maxSum;
}
function step() {
currentIdx++;
if (currentIdx >= nums.length) {
document.getElementById('statusMessage').className = 'status-message success';
document.getElementById('statusMessage').textContent =
`✅ Done! Maximum subarray sum: ${maxSum} (indices ${bestStart} to ${bestEnd})`;
document.getElementById('stepBtn').disabled = true;
stopAuto();
return;
}
const num = nums[currentIdx];
const extendSum = currSum + num;
const startFresh = num;
let decision;
if (startFresh > extendSum) {
currSum = startFresh;
subarrayStart = currentIdx;
decision = 'START FRESH';
} else {
currSum = extendSum;
decision = 'EXTEND';
}
if (currSum > maxSum) {
maxSum = currSum;
bestStart = subarrayStart;
bestEnd = currentIdx;
}
document.getElementById('statusMessage').textContent =
`Index ${currentIdx}: num = ${num}, extend (${extendSum}) vs start fresh (${startFresh}) → ${decision}`;
document.getElementById('decisionDisplay').innerHTML =
`<strong>At index ${currentIdx} (value: ${num}):</strong><br>` +
`Option 1 (Extend): ${currSum - num < 0 ? '' : '+'}${currSum - num} + ${num} = ${extendSum}<br>` +
`Option 2 (Start Fresh): ${num}<br>` +
`<strong>Decision: ${decision}</strong> → curr_sum = ${currSum}<br>` +
(currSum === maxSum && currentIdx === bestEnd ?
`<span style="color: #4caf50;">✨ New max_sum = ${maxSum}!</span>` :
`max_sum stays at ${maxSum}`);
history.push({idx: currentIdx, currSum, maxSum});
updateVariables();
renderArray();
renderChart();
}
function toggleAuto() {
if (autoInterval) {
stopAuto();
} else {
document.getElementById('autoBtn').textContent = 'Pause';
autoInterval = setInterval(() => {
if (currentIdx >= nums.length - 1) {
step();
stopAuto();
} else {
step();
}
}, 1200);
}
}
function stopAuto() {
if (autoInterval) {
clearInterval(autoInterval);
autoInterval = null;
}
document.getElementById('autoBtn').textContent = 'Auto Run';
}
function reset() {
stopAuto();
currSum = nums[0];
maxSum = nums[0];
currentIdx = 0;
subarrayStart = 0;
bestStart = 0;
bestEnd = 0;
history = [{idx: 0, currSum: nums[0], maxSum: nums[0]}];
document.getElementById('stepBtn').disabled = false;
document.getElementById('statusMessage').className = 'status-message';
document.getElementById('statusMessage').textContent = 'Click "Step" or "Auto Run" to start visualization';
document.getElementById('decisionDisplay').textContent = 'Waiting to start...';
init();
}
init();
</script>
</body>
</html>