TADM2E 8.25 - Revision history

Jporcelli1120 at 15:47, 22 October 2014

2014-10-22T15:47:24Z

2014-10-22T15:44:41Z

2014-10-22T15:42:03Z

2014-10-22T15:38:03Z

2014-10-22T15:36:59Z

2014-10-22T15:35:46Z

2014-10-22T15:35:05Z

2014-10-22T15:34:33Z

2014-10-22T15:33:41Z

2014-10-22T15:32:49Z

@@ Line 2: / Line 2: @@
 <source lang="java">
-	public static int[] maxsum(int i, int j, int[] a) {
+public static int[] maxsum(int i, int j, int[] a) {
-		int max = Integer.MIN_VALUE;
+	int max = Integer.MIN_VALUE;
-		int cur_max = Integer.MIN_VALUE;
+	int cur_max = Integer.MIN_VALUE;
-		int cm_i = i;
+	int cm_i = i;
-		int cm_j = i;
+	int cm_j = i;
-		int m_i = i;
-		int m_j = i;
+        int m_i = i;
-		for (; i <= j; i++) {
+	for (; i <= j; i++) {
-			int x = a[i];
+		int x = a[i];
-			if(cur_max + x > x){
+		if(cur_max + x > x){
-				cur_max += x;
+			cur_max += x;
-				cm_j++;
+			cm_j++;
-			}else{
+		}else{
-				cur_max = x;
+			cur_max = x;
-				cm_i = cm_j = i;
+			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;
+		}
+	}
 </source>

@@ 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.
-<code>
+<source lang="java">
-public static int[] maxsum(int i, int j, int[] a) {
+	public static int[] maxsum(int i, int j, int[] a) {
 		int max = Integer.MIN_VALUE;
 		int cur_max = Integer.MIN_VALUE;
@@ Line 33: / Line 33: @@
 		return new int[] {m_i, m_j, max};
+	}
-</code>
+</source>

@@ 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.
 <code>
-	public static int[] maxsum(int i, int j, int[] a) {
+public static int[] maxsum(int i, int j, int[] a) {
 		int max = Integer.MIN_VALUE;
 		int cur_max = Integer.MIN_VALUE;

@@ Line 2: / Line 2: @@
 <code>
 	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_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;
@@ Line 48: / Line 32: @@
 		return new int[] {m_i, m_j, max};
+	}
 </code>

@@ Line 7: / Line 7: @@
 		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 m_i = i;
 		for (; i <= j; i++) {
@@ Line 19: / Line 23: @@
 			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;
@@ Line 42: / Line 54: @@
 		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]);
+	}
+}
 </code>