Write program to find the sum of subarray within a one-dimensional array of numbers which has the largest sum.
source Code
package com.dsacode.Algorithm.dynamic;
public class MaximumValueContiguous {
public static void main(String[] args)throws Exception
{
int testCases = 3;
System.out.println("No of Maximum value array:" + testCases);
for(int i = 1 ; i <= testCases; i++){
int caseElements = i;
int elements[] = new int[caseElements];
for(int j = 0 ; j < caseElements; j++)
elements[j] = i+j;
MaximumValueContiguousSubsequence(elements);
}
}
public static void MaximumValueContiguousSubsequence(int elements[]) {
int counter[] = new int[elements.length];
int max[] = new int[elements.length];
int maxValue = elements[0];
int maxValueIndex = 0;
for(int i = 0; i < elements.length; i++) {
if(i == 0) {
counter[i] = 1;
max[i] = elements[i];
} else {
if(elements[i] > elements[i] + max[i-1]) {
counter[i] = 1;
max[i] = elements[i];
if(max[i] > maxValue) {
maxValue = max[i];
maxValueIndex = i;
}
}else{
counter[i] = counter[i-1] + 1;
max[i] = max[i-1] + elements[i];
if(max[i] > maxValue) {
maxValue = max[i];
maxValueIndex = i;
}
}
}
}
int end = maxValueIndex;
int start = end;
while(counter[maxValueIndex] != 1) {
if(counter[--maxValueIndex] == 1) {
start = maxValueIndex;
break;
}
}
System.out.println(start + " to " + end);
}
}
Output
No of Maximum value array: 3 0 to 0 0 to 1 0 to 2
Algorithm Explanation
 | Build the number of test cases and initialize the array. |
| Pass the array to the utility function and create two more arrays which hold the cache elements. |
| Calculate the Maximum Value Contiguous Subsequence and print the result. |
Time Complexity
| Best Case | Average Case | Worst Case |
|---|---|---|
| – | O(n) | – |