forked from larissalages/code_problems
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKadane_Algorithm.java
More file actions
64 lines (53 loc) · 2.03 KB
/
Kadane_Algorithm.java
File metadata and controls
64 lines (53 loc) · 2.03 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
/*
Copyright 2020 Sakshi Khachane
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
public class kadane_Algorithm
{
public static int kadane(int input[], int n) // Function implementing Kadane's Algorithm (array contains at least one positive number)
{
int current_max = 0;
int max_so_far = 0;
for(int i = 0; i < n; i++)
{
current_max = Math.max(0, current_max + input[i]);
max_so_far = Math.max(max_so_far, current_max);
}
return max_so_far; // Maximum subarray sum
}
public static void main(String[] args)
{
int n, max_subarray_sum;
int input[] = { -2, 1, -6, 4, -1, 2, 1, -5, 4 }; // Input array
n = input.length; // Size of array
int flag = 0; // Flag variable to check if all the numbers in array are negative or not
int largest_in_negative = input[0]; // Smallest_negative variable will store the maximum subarray sum if all the numbers are negative in array
for(int i = 0; i < n; i++) // Scanning each element in array
{
if(input[i] >= 0) // If any element is positive, kadane's algo can be applied
{
flag = 1;
break;
}
else if(input[i] > largest_in_negative) // If all the elements are negative, find the largest in them
largest_in_negative = input[i];
}
if(flag == 1) // Kadane's algo applicable
max_subarray_sum = kadane(input, n);
else
max_subarray_sum = largest_in_negative; // Kadane's algo not applicable,
// Hence the max_subarray_sum will be the largest number in array itself
System.out.println("Maximum Subarray Sum is " + max_subarray_sum);
}
}
/*
output : Maximum Subarray Sum is 6
*/