Let us code the solution to the problem we discussed yesterday for splitting a positive integer array into two as nearly equal sum as possible:
int TryGetPartition (List <int> A)
{
Assert ( A != null );
Assert ( A.All (x => x > 0));
int index = 0;
If ( A.count <= 1) return index;
int left = A [0];
int right = A [A.Count - 1];
int I = 1;
int j = n-2;
int retry = 0;
while ( i < j)
{
if ( left + A [i] <= right + A [j]){
right += A [j];
J = j - 1;
continue;
}
if ( left + A [i] <= right) { left += A [i]; I = I + 1; continue;}
if ( left > right + A [j]) { right += A [j]; j = j -1; continue;}
if ( left > right) { right += A [j]; j = j -1; continue;}
retry = retry + 1;
if ( retry > 3) { break; }
}
if ( i == j) {
}
If (left+A[I] <= right)
index = I+1;
Else
Index=I;
}
if ( i > j ) {
If (left <= right)
index = I-1;
Else
index = I;
}
return index;
}
No comments:
Post a Comment