FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Algorithms/src/divideandconquer/FindMaximumSubarray.java at master · jingedawang/Algorithms · GitHub
jingedawang
/
Algorithms
Public
Notifications
You must be signed in to change notification settings
Fork
17
Star
102
Code
Issues
3
Pull requests
0
Discussions
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Discussions
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Algorithms
/
src
/
divideandconquer
/
FindMaximumSubarray.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
100 lines (93 loc) · 3.26 KB
Breadcrumbs
Algorithms
/
src
/
divideandconquer
/
FindMaximumSubarray.java
Copy path
File metadata and controls
100 lines (93 loc) · 3.26 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
/**
* Copyright 2022 jingedawang
*/
package
divideandconquer
;
import
utils
.
ArrayPrinter
;
import
utils
.
ArrayGenerator
;
import
utils
.
Values3
;
/**
* Find maximum subarray problem.
*
* Find a subarray of an array whose elements have the biggest value when summed up.
*/
public
class
FindMaximumSubarray
{
/**
* Demo code.
*/
public
static
void
main
(
String
[]
args
) {
int
[]
arr
=
ArrayGenerator
.
randomArray
(-
10
,
10
,
20
);
System
.
out
.
println
(
"Find the maximum subarray of this array:"
);
ArrayPrinter
.
print
(
arr
);
FindMaximumSubarray
findMaximumSubarray
=
new
FindMaximumSubarray
();
Values3
<
Integer
,
Integer
,
Integer
>
values
=
findMaximumSubarray
.
findMaximumSubarray
(
arr
,
0
,
arr
.
length
-
1
);
System
.
out
.
println
();
System
.
out
.
println
(
"The maximum subarray is:"
);
ArrayPrinter
.
print
(
arr
,
values
.
value1
,
values
.
value2
-
values
.
value1
+
1
);
System
.
out
.
println
(
"Values in this subarray sum up to "
+
values
.
value3
+
"."
);
}
/**
* Find the maximum subarray in the given range.
* <p>
* This method uses the divided and conquer strategy and implemented in a recursive way.
*
* @param arr The sequence to be handled.
* @param low The start index of the range.
* @param high The end index of the range.
* @return A three value tuple, in which the values represent the start index, end index and the sum of the maximum
* subarray.
*/
public
Values3
<
Integer
,
Integer
,
Integer
>
findMaximumSubarray
(
int
[]
arr
,
int
low
,
int
high
) {
// Recursive termination condition.
if
(
high
==
low
) {
return
new
Values3
<>(
low
,
high
,
arr
[
low
]);
}
// Divide
int
mid
= (
low
+
high
) /
2
;
Values3
<
Integer
,
Integer
,
Integer
>
leftResult
=
findMaximumSubarray
(
arr
,
low
,
mid
);
Values3
<
Integer
,
Integer
,
Integer
>
rightResult
=
findMaximumSubarray
(
arr
,
mid
+
1
,
high
);
Values3
<
Integer
,
Integer
,
Integer
>
crossResult
=
findMaxCrossingSubarray
(
arr
,
low
,
mid
,
high
);
if
(
leftResult
.
value3
>=
rightResult
.
value3
&&
leftResult
.
value3
>=
crossResult
.
value3
) {
// The maximum subarray is located on the left side.
return
leftResult
;
}
else
if
(
rightResult
.
value3
>=
leftResult
.
value3
&&
rightResult
.
value3
>=
crossResult
.
value3
) {
// The maximum subarray is located on the right side.
return
rightResult
;
}
else
{
// The maximum subarray is crossing the middle point.
return
crossResult
;
}
}
/**
* Find the maximum subarray which crossing the middle point.
*
* @param arr The sequence to be handled.
* @param low The start index of the range.
* @param mid The index of the middle point.
* @param high The end index of the range.
* @return A three value tuple, in which the values represent the start index, end index and the sum of the maximum
* subarray which crossing the middle point.
*/
private
Values3
<
Integer
,
Integer
,
Integer
>
findMaxCrossingSubarray
(
int
[]
arr
,
int
low
,
int
mid
,
int
high
) {
int
leftSum
=
Integer
.
MIN_VALUE
;
int
sum
=
0
;
int
maxLeft
=
mid
;
for
(
int
i
=
mid
;
i
>=
low
;
i
--) {
sum
+=
arr
[
i
];
if
(
sum
>
leftSum
) {
leftSum
=
sum
;
maxLeft
=
i
;
}
}
int
rightSum
=
Integer
.
MIN_VALUE
;
sum
=
0
;
int
maxRight
=
mid
+
1
;
for
(
int
j
=
mid
+
1
;
j
<=
high
;
j
++) {
sum
+=
arr
[
j
];
if
(
sum
>
rightSum
) {
rightSum
=
sum
;
maxRight
=
j
;
}
}
return
new
Values3
<>(
maxLeft
,
maxRight
,
leftSum
+
rightSum
);
}
}
Back
|
FazBrowse Home
|
New Git URL