In Java use The Cubic maximum contiguous subsequence sum algorithm, the Quadrati
ID: 639909 • Letter: I
Question
In Java use The Cubic maximum contiguous subsequence sum algorithm, the Quadratic maximum contiguous subsequence sum algorithm, and the linear maximum contiguous subsequence sum algorithm to create one single application that compares the processing times of each algorithm against the same array of numbers. The application needs to be run with and array of five (5), twenty (20), fifty (50), and one hundred (100) random integers with the range of integers between -10 to 10.
* Cubic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSum( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
for( int j = i; j < a.length; j++ )
{
int thisSum = 0;
for( int k = i; k <= j; k++ )
thisSum += a[ k ];
if( thisSum > maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
}
return maxSum;
}
* Quadratic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSum( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
{
int thisSum = 0;
for( int j = i; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
}
}
return maxSum;
}
* Linear maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maximumSubsequenceSum( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
for( int i = 0, j = 0; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
}
return maxSum;
}
Explanation / Answer
/*
* The java program that displays the time for
* the three algorithms of cubic sum
* and displays the results against
* to 5,20,50 and 100 size arrays.
* */
//CubicSumAlgorithm.java
public class CubicSumAlgorithm
{
public static void main(String[] args)
{
//five (5), twenty (20), fifty (50), and one hundred (100) random
int[] five=new int[5];
int[] twenty=new int[20];
int[] fifty=new int[50];
int[] hundred=new int[100];
//Call the createRandomArray with 5,20,50 and 100 for three algorithms
createRandomArray(five);
createRandomArray(twenty);
createRandomArray(fifty);
createRandomArray(hundred);
System.out.printf("%-20s%-20s ","Start Time","End Time(in seconds)");
long startTime=System.nanoTime();
double sum=maxSubsequenceSum(five);
sum=maxSubsequenceSum(twenty);
sum=maxSubsequenceSum(fifty);
sum=maxSubsequenceSum(hundred);
long endTime=System.nanoTime();
//Converting from the nano seconds to seconds
System.out.println((double)startTime/ 1000000000.0+" "+(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maxSubsequenceSumOne(five);
sum=maxSubsequenceSumOne(twenty);
sum=maxSubsequenceSumOne(fifty);
sum=maxSubsequenceSumOne(hundred);
endTime=System.nanoTime();
//Converting from the nano seconds to seconds
System.out.println((double)startTime/ 1000000000.0+" "+(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maximumSubsequenceSumTwo(five);
sum=maximumSubsequenceSumTwo(twenty);
sum=maximumSubsequenceSumTwo(fifty);
sum=maximumSubsequenceSumTwo(hundred);
endTime=System.nanoTime();
//Converting from the nano seconds to seconds
System.out.println((double)startTime/ 1000000000.0+" "+(double)endTime/ 1000000000.0);
}
/*The method accepts a array of integers an its parameter
* and creats an array with random numbers in a range of
* -10 and 10.
* */
public static void createRandomArray(int[] a)
{
int minimum=-10;
int maximum=10;
for (int i = 0; i < a.length; i++)
{
int randomNum = minimum + (int)(Math.random()*maximum);
a[i]=randomNum;
}
}
/* Cubic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSum( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
for( int j = i; j < a.length; j++ )
{
int thisSum = 0;
for( int k = i; k <= j; k++ )
thisSum += a[ k ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
return maxSum;
}
/* Quadratic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSumOne( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
{
int thisSum = 0;
for( int j = i; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
}
return maxSum;
}
/* Linear maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maximumSubsequenceSumTwo( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
for( int i = 0, j = 0; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
}
return maxSum;
}
}
--------------------------------------------------------------------
Sample output:
Start Time End Time
3349.393082591 3349.394279416
3349.394831337 3349.394992491
3349.39504825 3349.395056219
Hope this helps you
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.