-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPrefixSumMSA.java
More file actions
32 lines (29 loc) · 972 Bytes
/
PrefixSumMSA.java
File metadata and controls
32 lines (29 loc) · 972 Bytes
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
package Arrays;
public class PrefixSumMSA {
public static void PrefixSum(int numbers[]){
int currsum = 0;
int maxSum = Integer.MIN_VALUE;
int prefix[] = new int[numbers.length];
prefix[0] = numbers[0];
//Calculate prefix array
for(int i=1; i<prefix.length; i++){
prefix[i] = prefix[i-1] + numbers[i];
}
for(int i=0; i<numbers.length; i++){
int start = i;
for(int j=i; j<numbers.length; j++){
int end = j;
currsum = start==0?prefix[end]:prefix[end]-prefix[start-1];
if(maxSum<currsum){
maxSum = currsum;
}
System.out.println();
}
}
System.out.println("The Max Sum is " + maxSum);
}
public static void main(String[] args) {
int numbers[] = {1,2,4,6,8,9};
PrefixSum(numbers);
}
}