כיצד להשתמש בחלוקה וכבש כדי לקבל את סכום המשנה הגדול ביותר, המוחזר כמערך

אני נתקל כעת בבעיה עם שאילתת הסכום המקסימלי של תת-מערך ממאמר זה לפי נושאי scaler. אני מנסה לברר כיצד לשים את המספרים ב-LRMax מבלי להשתמש בקוד המוער. כאשר LRMax[0] הוא האינדקס השמאלי של מערך maxsub, LRMax[1] הוא האינדקס הימני של מערך maxsub, ו-LRMax[2] הוא הסכום של מערך maxsub.
[code]
public class Main {

public static void main(String[] args) {
int[] values = {0, 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5,
-22, 15, -4, 7};
int low = 1; int high = 16; int mid = (low + high) / 2;

int[] LRMax = new int[3];

LRMax = maxSubarray(values, low, high);
System.out.println(LRMax[0] + " " + LRMax[1] + " " +LRMax[2]);
}

public static int[] maxSubarray(int[] values, int low, int high) { //returns LRMax: LRMax[0 and 1] -> left and right index of max subarray
// and LRMax[2] -> the crossing sub array's sum
int[] LRMax = new int[3];
//If the array contains one element, set all of LRMax to low.
if (high == low) {
LRMax[0] = 0;
LRMax[1] = 0;
LRMax[2] = low;
return LRMax;
}

//Find midpoint of the array
int mid = (low + high) / 2;

//Find maximum subarray sum for left subarray including middle element
int leftMax = Integer.MIN_VALUE;
int sum = 0;
for (int i = mid; i >= low; i--) {
sum += values[i];
if (sum > leftMax) {
leftMax = sum;
}
}

//Find maximum subarray sum for right subarray but not including middle element
int rightMax = Integer.MIN_VALUE;
sum = 0;
for (int i = mid + 1; i <= high; i++) {
sum += values[i];
if (sum > rightMax) {
rightMax = sum;
}
}

//Find maximum subarray sum for the left and right subarray, take maximum value
//int maxLeftRight = Integer.max(maxSubarray(values, low, mid), maxSubarray(values, mid + 1, high));

// return the maximum of the three
//return Integer.max(maxLeftRight, leftMax + rightMax)
LRMax[0] = ;
LRMax[1] = ;
LRMax[2] = ;

return LRMax;
}
}
[/code]
Source: https://www.scaler.com/topics/kadan?...

כותרת:
תוכן:
סמיילים:	הצג

כותרת:
תוכן:
סמיילים:	הצג

העבר לפורום:
סיבה: