The input to this problem is an array A[1...n] of real numbers. You need to find out what the highest value is that can be obtained by summing up all numbers of a contiguous subsequence A[i], A[i+1],...A[j] of A. If A does not contain negative numbers, the problem is trivial and can be solved by summing up all the elements of A. It becomes more tricky when A contains a mix of positive and negative numbers though.
This problem is same as maximum contiguous subarray sum problem.
For instance, for A = [-2,11,-4,13,-5,-2], the solution is 20 (11-4+13=20).
Brute force Approach :
package dp;
public class MaximumValueContiguousSubsequence {
public static void main(String[] args) {
int[] arr = new int[] {-2, 11, -4, 13, -5, 2};
long startTime = System.nanoTime();
System.out.println(FindMaximumValue(arr));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FindMaximumValue(int[] arr) {
int max = 0;
for(int i=0;i<arr.length;i++) {
for(int j=i+1;j<arr.length;j++) {
int sum = 0;
//Checking all possible combinations
for(int k=i;k<=j;k++) {
sum+=arr[k];
if(sum>max)
max = sum;
}
}
}
return max;
}
}
output:
20
Total Time (nanoseconds) : 353793
The Time complexity of the above solution is O(n^3) and space complexity is O(1).
Can we improve the above solution?
Yes, we can by using only 2 loops and use the already computed result.
package dp;
public class MaximumValueContiguousSubsequence {
public static void main(String[] args) {
int[] arr = new int[] {-2, 11, -4, 13, -5, 2};
long startTime = System.nanoTime();
System.out.println(FindMaximumValue(arr));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FindMaximumValue(int[] arr) {
int max = 0;
for(int i=0;i<arr.length;i++) {
int sum = 0;
for(int j=i;j<arr.length;j++) {
sum+=arr[j];
if(sum>max)
max = sum;
}
}
return max;
}
}
output:
20
Total Time (nanoseconds) : 306218
The time complexity of the above solution is O(n^2) and space complexity is O(1).
Can we improve the above solution even further?
Yes by using Dynamic Programming.
package dp;
public class MaximumValueContiguousSubsequence {
public static void main(String[] args) {
int[] arr = new int[] {-2, 11, -4, 13, -5, 2};
long startTime = System.nanoTime();
System.out.println(FindMaximumValue(arr));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
private static int FindMaximumValue(int[] arr) {
int[] M = new int[arr.length+1];
if(arr.length == 0)
return 0;
if(arr.length == 1)
return arr[0];
if(arr[0]>0)
M[0] = arr[0];
else
M[0] = 0;
for(int i=1;i<arr.length;i++) {
if(arr[i]+M[i-1]>0)
M[i]=arr[i]+M[i-1];
else
M[i]=0;
}
int max = Integer.MIN_VALUE;
for(int i=0;i<M.length;i++)
{
if(max < M[i])
max = M[i];
}
return max;
}
}
output:
20
Total Time (nanoseconds) : 158206
Time Complexity of the above solution is O(n) and Space Complexity is also O(n).
