Difference between revisions of "TADM2E 8.25"

From Algorithm Wiki
Jump to: navigation, search
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
This is just a special case of the maximum contiguous sum problem. Instead of computing the result for 0,n instead we compute for i,j. We use the same logic, but as per the question we return 3 values indicating the index positions i', j', and max for the maximum sum of the i'th through j'th numbers.  Note that this solution has a worst case running time of O(n), and requires constant additional space. Also note that this solution does not appear, to me, to really be a 'dynamic programming' algorithm.
 
This is just a special case of the maximum contiguous sum problem. Instead of computing the result for 0,n instead we compute for i,j. We use the same logic, but as per the question we return 3 values indicating the index positions i', j', and max for the maximum sum of the i'th through j'th numbers.  Note that this solution has a worst case running time of O(n), and requires constant additional space. Also note that this solution does not appear, to me, to really be a 'dynamic programming' algorithm.
  
<code>
+
<source lang="java">
public class Solution {
+
public static int[] maxsum(int i, int j, int[] a) {
 
+
int max = Integer.MIN_VALUE;
public static int[] maxsum(int i, int j, int[] a) {
+
int cur_max = Integer.MIN_VALUE;
 
 
int max = Integer.MIN_VALUE;
 
 
 
int cur_max = Integer.MIN_VALUE;
 
 
int cm_i = i;
 
 
 
int cm_j = i;
 
 
                int m_i = i;
 
 
 
                int m_j = i;
+
int cm_i = i;
 
+
int cm_j = i;
for (; i <= j; i++) {
+
 +
        int m_i = i;
 +
int m_j = i;
  
int x = a[i];
+
for (; i <= j; i++) {
 +
int x = a[i];
 
 
if(cur_max + x > x){
+
if(cur_max + x > x){
 
+
cur_max += x;
cur_max += x;
+
cm_j++;
 
+
}else{
cm_j++;
+
cur_max = x;
 
+
cm_i = cm_j = i;
}else{
+
}
 
 
cur_max = x;
 
 
 
cm_i = cm_j = i;
 
 
 
}
 
 
 
if(cur_max > max){
+
if(cur_max > max){
 
+
m_i = cm_i;
m_i = cm_i;
+
m_j = cm_j;
 
 
m_j = cm_j;
 
 
 
max = cur_max;
+
max = cur_max;
}
 
 
 
 
}
 
}
 
return new int[] {m_i, m_j, max};
 
 
}
 
 
public static void main(String[] args) {
 
 
int[] a = new int[]{31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
 
 
int[] ijmax = maxsum(5, a.length -1, a);
 
 
System.out.printf("i=%d, j=%d, sum=%d\n", ijmax[0], ijmax[1], ijmax[2]);
 
  
 
}
 
}
  
 +
return new int[] {m_i, m_j, max};
 
}
 
}
</code>
+
</source>

Latest revision as of 15:47, 22 October 2014

This is just a special case of the maximum contiguous sum problem. Instead of computing the result for 0,n instead we compute for i,j. We use the same logic, but as per the question we return 3 values indicating the index positions i', j', and max for the maximum sum of the i'th through j'th numbers. Note that this solution has a worst case running time of O(n), and requires constant additional space. Also note that this solution does not appear, to me, to really be a 'dynamic programming' algorithm.

public static int[] maxsum(int i, int j, int[] a) {
	int max = Integer.MIN_VALUE;
	int cur_max = Integer.MIN_VALUE;
 
	int cm_i = i;
	int cm_j = i;
 
        int m_i = i;
	int m_j = i;
 
	for (; i <= j; i++) {
		int x = a[i];
 
		if(cur_max + x > x){
			cur_max += x;
			cm_j++;
		}else{
			cur_max = x;
			cm_i = cm_j = i;
		}
 
		if(cur_max > max){
			m_i = cm_i;
			m_j = cm_j;
 
			max = cur_max;
		}
 
	}
 
	return new int[] {m_i, m_j, max};
}