HTW Berlin Fachbereich 4 Internationaler Bachelor Studiengang Internationale Medieninformatik (Bachelor) Info 2: Informatik II Summer Term 2023

Comparable[] a = ......
int low = 0;
int high = a.length-1;
int mid;
while (low <= high) {
   mid = (low + high)/2; 
   if (a[mid].compares (x) < 0) {
      low = mid + 1;
   } else if (a[mid].compares (x) > 0) {
      high = mid + 1;
   } else { return mid;}
}
throw new ItemNotFound ("BinSearch fails");

int maxSum = 0; 
int start, end = -1;
for (int i=0; i < a.length; i++){
    for (int j = i; j < a.length; j++){
        int thisSum = 0;
        for (int k=i; k <=j; k++){

            thisSum += a[k];

        }

        if (thisSum > maxSum) {

           maxSum=thisSum;

           start = i;

           end = j;
        }

    }
}

int maxSum = 0; 
int start, end = -1;
for (int i = 0; i < a.length; i++) {
    int thisSum = 0;
    for (int j=i; j < a.length; j++) {
        thisSum += a[j];
        if (thisSum > maxSum) {
           maxSum = thisSum:
           start = i;
           end = j;
        }
    }
}

Continuous Subsequence Sum: Linear

int maxSum, thisSum = 0;
for (int i=0, j=0; j < a.length; j++) {
    thisSum += a[j];
    if (thisSum > maxSum) {
       -- remember it
       maxSum = thisSum:
       start = i;
       end = j;
    } else if (thisSum < 0) {
              i = j+1;
              thisSum = 0;
           }
}