Dynamic programming

Maximum Value Contiguous Subsequence

Pinterest LinkedIn Tumblr

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 CaseAverage CaseWorst Case
O(n)

Reference

  1. http://courses.csail.mit.edu/6.006/fall10/handouts/dpproblems-sol.pdf
  2. http://www.cs.cmu.edu/afs/cs/academic/class/15210-f13/www/lectures/lecture04.pdf
  3. https://tkramesh.wordpress.com/2011/03/09/dynamic-programming-maximum-sum-contiguous-subsequence/

Write A Comment