首页 > 代码库 > 最大子序列问题

最大子序列问题

2024-07-15 13:44:06   217人阅读

最大子数组问题

定义

         给定整数A1, A2, …, An(其中可能是负数)，求k的最大值和序列的起始位置（为了方便起见，如果所有整数均为负数，则最大子序列和为0），使用四种算法（根据运行时间区分）解决这个问题。

运行时间为θ(n3)

         使用了三个for循环，在最坏情况下，运行时间为θ(n3)

C语言实现代码

#include<stdio.h>#define LEN(array) (sizeof(array)/sizeof(array[0])) void maxsubarray(int *array, int len, int *, int *);main(){    int array[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};    int i, start, end;        printf("原始数组:\n");    for (i = 0; i < LEN(array); i++)        printf("%5d", array[i]);            putchar(‘\n‘);    maxsubarray(array, LEN(array), &start, &end);    printf("最大子序列的起始位置为：%d, 终止位置为：%d\n", start+1, end+1);    printf("最大子序列为: ");            for (i = start; i <= end; i++)        printf("%5d", array[i]);    putchar(‘\n‘);    putchar(‘\n‘);}void maxsubarray(int *array, int len, int *start, int *end){    int i, j, k, sum, maxsum;        maxsum = 0;    for (i = 0; i < len; i++){        for (j = i; j < len; j++){            sum = 0;            for (k = i; k <= j; k++){                sum += array[k];                if (sum > maxsum){                    maxsum = sum;                    *start = i;                    *end = j;                }                                }        }    }        printf("\n子序列的求和最大值为： %d\n", maxsum);        }

 

运行时间为θ(n2)

         使用了两个for循环，最坏情况下运行时间为θ(n2)

C语言实现代码

#include<stdio.h>#define LEN(array) (sizeof(array)/sizeof(array[0])) void maxsubarray(int *array, int len, int *, int *); main(){         int array[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};         int i, start, end;                 printf("原始数组:\n");         for (i = 0; i < LEN(array); i++)                   printf("%5d", array[i]);                           putchar(‘\n‘);         maxsubarray(array, LEN(array), &start, &end);         printf("最大子序列的起始位置为：%d, 终止位置为：%d\n", start+1, end+1);         printf("最大子序列为: ");                 for (i = start; i <= end; i++)                   printf("%5d", array[i]);         putchar(‘\n‘);         putchar(‘\n‘);} void maxsubarray(int *array, int len, int *start, int *end){         int i, j, sum, maxsum;                 maxsum = 0;         for (i = 0; i < len; i++){                   sum = 0;                   for (j = i; j < len; j++){                                                               sum += array[j];                                     if (sum > maxsum){                                               maxsum = sum;                                               *start = i;                                               *end = j;                                     }                                                                                          }         }                 printf("\n子序列的求和最大值为： %d\n", maxsum);             }

 

运行时间为θ(nlgn)

         使用分治法求解：

         假设我们要寻找子数组A[low..high]的最大子数组，使用分治技术意味着要将子数组划分为两个规模尽量相等的子数组，也就是说，要找到子数组的中央位置mid，然后考虑求解两个子数组A[low..high]的任何连续子数组A[i..j]所处的位置必然是以下三种情况之一：

  1. 完全位于子数组A[low, mid]中，因此，low <= i <= j <= mid
  2. 完全位于子数组A[mid+1, high]中，因此mid <= i <= j <= high
  3. 跨越了重点，因此low <= i <= mid < j <= high

递归地求解A[low..mid]和A[mid+1..high]的最大子数组，因为这两个子问题仍然是最大子数组问题，只是规模更小

伪代码

         注意求出跨越中点的最大子数组问题并非原问题的更小实例，因为它加入了限制，求出的子数组必须跨越中点，任何跨越中点的子数组都由两个子数组A[i..mid]和A[mid+1..j]组成，其中low<= i <= mid且mid< j <= high，因此，只需要找出形如A[i..mid]和A[mid+1..j]的最大子数组，然后将其合并即可，过程FIND-MAX-CORSSING-SUBARRAY接收数组A和下标low, mid和high为输入，返回一个下标元组划定跨越中点的最大子数组的边界，并返回最大子数组中值的和

         先求出左半部A[low..mid]的最大子数组，再求出右半部A[mid+1..high]的最大子数组，然后返回子数组A[max-left..max-right]

       

  FIND-MAX-CORSSING-SUBARRAY(A, low, mid, high)         left-sum = A[mid]         sum = 0         for i = mid downto low                   sum = sum + A[i]                   if sum > left-sum                            left-sum = sum                            max-left = i         right-sum = A[mid+1]         sum = 0         for j = mid+1 to high                   sum += A[j]                   if sum > right-sum                            right-sum = sum                            max-right = j         return (max-left, max-right, left-sum+right-sum)

 

求解最大子数组问题的分治算法的伪代码：

FIND-MAXIMUM-SUBARRAY(A, low, high)         if high == low                   return(low, high, A[low])         else mid = (low + high) / 2                   (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)                   (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid+1, high)                   (cross-low, corss-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)                   if left-sum >= right-sum and left-sum >= corss-sum                            return (left-low, left-high, left-sum)                   else if right-sum >= left-sum and right-sum >= cross-sum                            return (right-low, right-high, right-sum)                   else                            return (corss-low, cross-high, cross-sum)

 

C语言代码实现

#include<stdio.h>#define LEN(array) (sizeof(array)/sizeof(array[0])) int maxsubarray(int *, int , int , int *, int *);int crosssubarray(int *array, int low, int mid, int high, int *begin, int *end); main(){         int array[] = {13, -3, -25, 20, -3, -16, 23, -18, -20, -7, 12, -5, -22, 15, -4};         int i, start, end, sum;                 printf("原始数组:\n");         for (i = 0; i < LEN(array); i++)                   printf("%5d", array[i]);                           putchar(‘\n‘);         sum = maxsubarray(array, 0, LEN(array)-1, &start, &end);         printf("最大子序列的和为：%d\n", sum);         printf("最大子序列的起始位置为：%d, 终止位置为：%d\n", start+1, end+1);         printf("最大子序列为: ");                 for (i = start; i <= end; i++)                   printf("%5d", array[i]);         putchar(‘\n‘);         putchar(‘\n‘);} int maxsubarray(int *array, int low, int high, int *begin, int *end){         int mid, left_sum, right_sum, cross_sum;         int left_low, left_high, right_low, right_high, cross_low, cross_high;                 if (low == high){                   return array[low];                   *begin = low;                   *end = high;         }                           mid = (low + high) / 2;         left_sum = maxsubarray(array, low, mid, begin, end);         left_low = *begin;         left_high = *end;         right_sum = maxsubarray(array, mid+1, high, begin, end);         right_low = *begin;         right_high = *end;         cross_sum = crosssubarray(array, low, mid, high, begin, end);         cross_low = *begin;         cross_high = *end;                 if (left_sum > right_sum && left_sum > cross_sum){                   *begin = left_low;                   *end = left_high;                   return left_sum;         }                           else if (right_sum > left_sum && right_sum > cross_sum){                   *begin = right_low;                   *end = right_high;                   return right_sum;         }                         else{                   *begin = cross_low;                   *end = cross_high;                   return cross_sum;                      }                           } int crosssubarray(int *array, int low, int mid, int high, int *begin, int *end){         int left_sum, right_sum, sum, i, j;         left_sum = array[mid];         sum = 0;         *begin = mid;         *end = mid+1;         for (i = mid; i >= low; i--){                   sum += array[i];                   if (sum > left_sum){                            left_sum = sum;                            *begin = i;                   }         }         right_sum = array[mid+1];         sum = 0;         for (j = mid+1; j <= high; j++){                   sum += array[j];                   if (sum > right_sum){                            right_sum = sum;                            *end = j;                   }         }         return left_sum + right_sum;}

 

运行时间为θ(n)

         只使用了一次for循环，注意，该算法只适用于数组原来的所有元素的求和值大于0，如果原来的数组的所有元素的求和值小于0,则不适用于本算法

C语言代码实现

#include<stdio.h>#define LEN(array) (sizeof(array)/sizeof(array[0]))void maxsubarray(int *array, int len, int *, int *);main(){//      int array[] = {13, -3, -25, 20, -3, -16, 23, -18, -20, -7, 12, -5, -22, 15, -4};//      int array[] = {13, -3, -25};         int array[] = {13, -3, -25, 55, -34};         int i, start, end;                 printf("原始数组:\n");         for (i = 0; i < LEN(array); i++)                   printf("%5d", array[i]);                        putchar(‘\n‘);         maxsubarray(array, LEN(array), &start, &end);         printf("最大子序列的起始位置为：%d, 终止位置为：%d\n", start+1, end+1);         printf("最大子序列为: ");                 for (i = start; i <= end; i++)                   printf("%5d", array[i]);         putchar(‘\n‘);         putchar(‘\n‘);} void maxsubarray(int *array, int len, int *start, int *end){         int i, sum, maxsum, temp;
               sum = maxsum = 0;         temp = 0;         for (i = 0; i < len; i++){                   sum += array[i];                   if (sum > maxsum){                            maxsum = sum;                            *end = i;                            *start = temp;                   }                   else if (sum < 0){                            //temp的值就是最大子序列的起始位置                            sum = 0;                            temp = i + 1;                   }         }                printf("\n子序列的求和最大值为： %d\n", maxsum);             }

 


联系
我们