FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java_Learning/17_Arrays(Part2)/MaxSubarraySum.java at main · TORRYNN/Java_Learning · GitHub
TORRYNN
/
Java_Learning
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
1
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java_Learning
/
17_Arrays(Part2)
/
MaxSubarraySum.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
100 lines (89 loc) · 3.27 KB
Breadcrumbs
Java_Learning
/
17_Arrays(Part2)
/
MaxSubarraySum.java
Copy path
File metadata and controls
100 lines (89 loc) · 3.27 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
public
class
MaxSubarraySum
{
public
static
void
maxSum
(
int
[]
arr
) {
// Currentsum variable will track this currentsum of the value
int
currentSum
=
0
;
// we intialised the max sum with the minimum value.
int
maxSum
=
Integer
.
MIN_VALUE
;
// this loop is for all the possible starting indices
for
(
int
i
=
0
;
i
<
arr
.
length
;
i
++) {
// this loop is for ending indices
for
(
int
j
=
i
;
j
<
arr
.
length
;
j
++) {
currentSum
=
0
;
// This loop is for calculating the currentsum
for
(
int
k
=
i
;
k
<=
j
;
k
++) {
currentSum
+=
arr
[
k
];
}
System
.
out
.
println
(
currentSum
);
if
(
currentSum
>
maxSum
) {
maxSum
=
currentSum
;
}
}
}
System
.
out
.
println
(
"MaxSum= "
+
maxSum
);
}
// -----------------------------------------------------------------
// this is prefix sum approach in this approach first we create an array with cumulative sum
public
static
void
maxsum1
(
int
[]
arr
) {
int
currentSum
=
0
;
int
maxSum
=
Integer
.
MIN_VALUE
;
int
prefix
[] =
new
int
[
arr
.
length
];
prefix
[
0
] =
arr
[
0
];
for
(
int
i
=
1
;
i
<
arr
.
length
;
i
++) {
prefix
[
i
] =
prefix
[
i
-
1
] +
arr
[
i
];
}
for
(
int
i
=
0
;
i
<
arr
.
length
;
i
++) {
for
(
int
j
=
i
;
j
<
arr
.
length
;
j
++) {
currentSum
=
i
==
0
?
prefix
[
j
] :
prefix
[
j
] -
prefix
[
i
-
1
];
}
maxSum
=
Math
.
max
(
maxSum
,
currentSum
);
}
System
.
out
.
println
(
"Max sum using prefix array = "
+
maxSum
);
}
// -----------------------------------------------------------------
// ! This one does not handle the case when all the elements of the array are
// negative.
public
static
void
kadane
(
int
arr
[]) {
int
maxSum
=
Integer
.
MIN_VALUE
;
int
currentSum
=
0
;
for
(
int
i
=
0
;
i
<
arr
.
length
;
i
++) {
currentSum
+=
arr
[
i
];
if
(
currentSum
<
0
) {
currentSum
=
0
;
}
maxSum
=
Math
.
max
(
maxSum
,
currentSum
);
}
System
.
out
.
println
(
"Max sum using Kadane's Algorithm = "
+
maxSum
);
}
public
static
void
kadane1
(
int
arr
[]) {
int
maxSum
=
Integer
.
MIN_VALUE
;
int
currentSum
=
0
;
int
start
=
0
,
end
=
0
,
tempstart
=
0
;
for
(
int
i
=
0
;
i
<
arr
.
length
;
i
++) {
currentSum
+=
arr
[
i
];
if
(
currentSum
>
maxSum
) {
maxSum
=
currentSum
;
start
=
tempstart
;
end
=
i
;
}
if
(
currentSum
<
0
) {
currentSum
=
0
;
tempstart
=
i
+
1
;
}
}
// Print the subarray with the maximum sum
System
.
out
.
print
(
"Subarray with the maximum sum: "
);
for
(
int
i
=
start
;
i
<=
end
;
i
++) {
System
.
out
.
print
(
arr
[
i
] +
" "
);
}
System
.
out
.
println
();
// Print the maximum sum
System
.
out
.
println
(
"Max sum using Kadane's Algorithm = "
+
maxSum
);
}
public
static
void
main
(
String
[]
args
) {
int
arr
[] = {
2
,
4
,
6
,
8
,
10
};
maxSum
(
arr
);
maxsum1
(
arr
);
kadane
(
arr
);
kadane1
(
arr
);
}
}
Back
|
FazBrowse Home
|
New Git URL