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) | – |