max sum of contiguous subsequence

max sum of contiguous subsequence

dp

S[k+1] = max{S[k] + A[k+1], A[k+1]}
we also need to record start and end position of the subsequence

S[0] = 0;
start[0] = end[0] = 0;
S[1] = A[0] ;
start[1] = end[1] = 0
S[2] = S[1]+ A[1] > A[1] ? S[1]+A[1] : A[1];
start[2] = 0 || 1
end [2]= 1

..
S[k+1] = S[k] + A[k+1] > A[k+1] ? S[k] + A[k+1] : A[k+1]

public int getMax( int[] Arr, int[] result, int[] start, int[] end )
{
result[0] = 0;
result[1] = 0;
start[0] = end[0] = 0;
start[1] = end[1] = 0;

int max = Integer.MIN+_VALUE;
int index;
for( int i = 2; i < Arr.length+1; i++)
{
if( result[i-1] + Arr[i] > Arr[i] )
{
result[i] = result[i-1] + Arr[i];
start[i] = start[i-1];
end[i] = i;
}
else
{
result[i] = Arr[i];
start[i] = i;
end[i] = i;
}
if( result[i] > max )
{
max = result[i];
index = i;
}
}
return index;
}

public static void main( String[] args )
{
int[] arr = new int[10];
int[] result = new int[10];
int[] start, int[] end;

int index = getMax( arr, result, start, end );
System.out.println( result[index], start[index], end[index] );
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s