Maximum Subsequence: The book’s author talked about the O(N) solution to the max
ID: 3848686 • Letter: M
Question
Maximum Subsequence: The book’s author talked about the O(N) solution to the maximum subsequence problem – and it is implemented such that it only returns the maximum sum. Modify this solution so that it returns an MSPAnswer object, where an MSPAnswer contains:
1) the starting index - i
2) the ending index - j
3) the max sum
................Sample Code........
1
Algorithm Analysis
2
3 */
4 public static int maxSubSum4( int [ ] a )
5{
6 int maxSum = 0, thisSum = 0;
7
8 for( int j = 0; j < a.length; j++ )
9{
10
11
12
13
14
15
16
17
18
19 }
Explanation / Answer
class Maximumsubsequence {
public static int methodmss( int[] elements, int len)
{
int i, j;
int maximun = 0;
int[] inarr= new int[len];
for ( i = 0; i < len; i++ ){
inarr[i] = elements[i];
}
for ( i = 1; i < len; i++ )
for ( j = 0; j < i; j++ )
if ( elements[i] > elements[j] &&
inarr[i] < inarr[j] + elements[i])
inarr[i] = inarr[j] + elements[i];
for ( i = 0; i < len; i++ )
if ( maximun< inarr[i] )
maximun = inarr[i];
return maximun;
}
}
allmain.java
import java.util.*;
import java.awt.*;
public class allmain {
public static void main(String args[]){
int elements[] = new int[]{10,5,3,4};
Maximumsubsequence s=new Maximumsubsequence();
int m= s.methodmss(elements, elements.length);
System.out.println("max sequence is="+m);
}
}
output:
max sequence is=10