浙江大学数据结构陈越 第一讲 数据结构和算法

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

int fibonacci(int n) {
    int a = 0, b = 1, next, i;
    if (n == 0)
        return a;
    for (i = 2; i <= n; i++) {
        next = a + b;
        a = b;
        b = next;
    }
    return b;
}

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 矩阵的抽象数据类型定义
template <typename T>
class Matrix {
public:
    // 构造函数，创建指定行列的矩阵
    Matrix(int rows, int cols);
    // 析构函数，释放矩阵内存
    ~Matrix();
    // 获取矩阵的行数
    int getRows() const;
    // 获取矩阵的列数
    int getCols() const;
    // 获取矩阵指定位置的元素
    T getElement(int row, int col) const;
    // 设置矩阵指定位置的元素
    void setElement(int row, int col, T value);
    // 矩阵加法
    Matrix<T> add(const Matrix<T>& matrix) const;
    // 矩阵减法
    Matrix<T> subtract(const Matrix<T>& matrix) const;
    // 矩阵乘法
    Matrix<T> multiply(const Matrix<T>& matrix) const;
    // 转置矩阵
    Matrix<T> transpose() const;
    // 打印矩阵
    void print() const;
private:
    int rows;  // 矩阵的行数
    int cols;  // 矩阵的列数
    T** data;  // 存储矩阵元素的二维数组指针
};

#include <iostream>
//KEY: use algorithm--Divide and Conquer;
using namespace std;
int *Init_array(int n);
int max(int a, int b, int c);
int divideseq(int *p, int left, int right);
int MaxSub(int *p, int n);
int main()
{
  int n, i = 0;
  cin >> n;
  int *p = Init_array(n);
  
  cout << MaxSub(p, n) << endl;
  delete[] p;
  return 0;
}
int* Init_array(int n)    //initialize array;
{
  int *pArray = new int[n];
  int i = 0;
  while (i < n)
    cin >> pArray[i++];
  return pArray;
}
int max(int a, int b, int c)
{
  return (a>b ? (a > c ? a : c) : (b < c ? c : b));
}
int divideseq(int *p, int left, int right)
{
  int i, maxboaderleft, maxboaderright;
  int leftboader = 0, rightboader = 0;
  if (left == right)  //it means only one data, the ending condition;
  {
    if (p[left] > 0)
      return p[left];
    else
      return 0;
  }
  int center = (left + right) / 2;
  int maxleft = divideseq(p, left, center);   // use 'recursion' to get the max left value;
  int maxright = divideseq(p, center + 1, right);
  maxboaderleft = 0;  
  for (i = center; i >= left; i--)    // get left boader max value, and right value, sum them.
  {
    leftboader += p[i];
    if (leftboader > maxboaderleft)   //so we get the value including the left and the right;
      maxboaderleft = leftboader;
  }
  maxboaderright = 0;
  for (i = center + 1; i <= right; i++)
  {
    rightboader += p[i];
    if (rightboader > maxboaderright)
      maxboaderright = rightboader;
  }
  return max(maxleft, maxright, maxboaderleft + maxboaderright);
}
int MaxSub(int *p, int n)
{
  return divideseq(p, 0, n - 1);
}

int main(){
  int n;
  int a[100000+5];
  cin>>n;
  for(int i=0;i<n;i++)
    cin>>a[i];
  MaxSubseqSum1(n,a);
  MaxSubseqSum2(n,a);
  MaxSubseqSum3(n,a);
  MaxSubseqSum4(n,a);
  MaxSubseqSum5(n,a);
  return 0;
}

/* 方法一：确定子列的首部和尾部，再遍历累加，时间复杂度 O(n^3)*/
int MaxSubseqSum1(int n,int a[]){
  int max = 0;
  for(int i=0;i<n;i++){   // 控制子列的尾部
    for(int k=0;k<i;k++){   // 控制子列的头部
      int tmpSum = 0;   //临时存放头部到尾部子列和
      for(int j=k;j<=i;j++){   
        tmpSum+=a[j]; 
      }
      if(max < tmpSum)
        max = tmpSum;
    }
  }
  return max;
}
容易想到，复杂度也高，O ( n 3 ) O(n^3)O(n 3 )

/* 方法二：确定子列的首部，逐个累加，时间复杂度 O(n^2)*/ 
int MaxSubseqSum2(int n,int a[]){
  int max = 0;
  for(int i=0;i<n;i++){   // 控制子列的首部
    int tmpSum = 0;  // 当前子列和
    for(int j=i;j<n;j++){  // 控制子列的尾部
      tmpSum+=a[j];
      if(max < tmpSum)
        max = tmpSum;
    }
  }
  return max;
}
把之前控制尾部的循环和求解子列和的循环融合了，复杂度为 O ( n 2 ) O(n^2)O(n 2)

/* 方法三：确定子列的结尾，逐个减去子列前的数，时间复杂度 O(n^2)*/ 
int MaxSubseqSum3(int n,int a[]){
  int sum[100000+5];
  int max = 0;
  sum[0]=a[0];
  for(int i=1;i<n;i++)   // 预处理保存前 n 个数之和
    sum[i]=sum[i-1]+a[i];
  for(int i=0;i<n;i++){   // 控制尾部
    int tmpSum = sum[i];
    for(int j=0;j<=i;j++){   // 控制首部，每一次减去当前值即首尾子列和
      if(max < tmpSum)
        max = tmpSum;
      tmpSum-=a[j]; 
    }
  }
  return max;
}
把之前控制首部的循环和求解子列和的循环融合了，复杂度为 O ( n 2 ) O(n^2)O(n 2  )

/* 方法四：递归分成两份，分别求每个分割后最大子列和，时间复杂度为 O(n*logn)*/
/* 返回三者中最大值*/
int Max3(int A,int B,int C){
  return (A>B)?((A>C)?A:C):((B>C)?B:C);
}
/* 分治*/
int DivideAndConquer(int a[],int left,int right){
  
  /*递归结束条件：子列只有一个数字*/
  // 当该数为正数时，最大子列和为其本身
  // 当该数为负数时，最大子列和为 0
  if(left == right){
    if(0 < a[left])  
      return a[left];
    return 0;
  }
  
  /* 分别递归找到左右最大子列和*/ 
  int center = (left+right)/2; 
  int MaxLeftSum = DivideAndConquer(a,left,center);
  int MaxRightSum = DivideAndConquer(a,center+1,right);
  
  /* 再分别找左右跨界最大子列和*/
  int MaxLeftBorderSum = 0;
  int LeftBorderSum = 0;
  for(int i=center;i>=left;i--){  //应该从边界出发向左边找
    LeftBorderSum += a[i];
    if(MaxLeftBorderSum < LeftBorderSum)
      MaxLeftBorderSum = LeftBorderSum; 
  }
  int MaXRightBorderSum = 0;
  int RightBorderSum = 0;
  for(int i=center+1;i<=right;i++){  // 从边界出发向右边找
    RightBorderSum += a[i];
    if(MaXRightBorderSum < RightBorderSum)
      MaXRightBorderSum = RightBorderSum;
  }
  
  /*最后返回分解的左边最大子列和，右边最大子列和，和跨界最大子列和三者中最大的数*/
  return Max3(MaxLeftSum,MaxRightSum,MaXRightBorderSum+MaxLeftBorderSum);
}
int MaxSubseqSum4(int n,int a[]){
  return DivideAndConquer(a,0,n-1);
}
时间复杂度 T ( n ) = 2 T ( T 2 ) + c ⋅ n ， T ( 1 ) = O ( 1 ) T(n) = 2T(\frac {T}{2}) + c·n ，T(1) = O(1)T(n)=2T( 
T
 )+c⋅n，T(1)=O(1) ，即 T ( n ) = O ( n l o g n ) T(n) = O(nlogn)T(n)=O(nlogn)

/* 方法五：直接累加，如果累加到当前的和为负数，置当前值或0，时间复杂度为 O(n)*/ 
int MaxSubseqSum5(int n,int a[]){
  int max = 0;
  int tmpSum=0;
  for(int i=0;i<n;i++){
    tmpSum+=a[i];
    if(tmpSum<0){
      tmpSum=0;
    }else if(max < tmpSum){
      max = tmpSum;
    }
  }
  return max;
}

#include<iostream>
using namespace std;
int main(){
  int n;
  int a[100000+5];
  cin>>n;
  for(int i=0;i<n;i++)
    cin>>a[i];
  int left = 0;
  int tmpleft = 0;
  int right = n-1;
  int max =0;
  int tmpSum=0;
  for(int i=0;i<n;i++){
    tmpSum+=a[i];
    if(tmpSum<0){
      tmpSum=0;
      tmpleft = i+1;   // 开头的数就在这段被抛弃子序列的下一个 
    }else if(max < tmpSum){
      max = tmpSum;        
      left = tmpleft;   // 每次更新最大值也就确定了一段子序列，保存此时的开头 
      right = i;       // 结尾的数就在每次更新最大值时 
    }
  }
  if(max>=0)
    cout<<max<<" "<<a[left]<<" "<<a[right];
  else
    cout<<0<<" "<<a[0]<<" "<<a[n-1];
  return 0;
}

代码（cpp）
Position BinarySearch( List L, ElementType X ){
  Position left = 1;
  Position right = L->Last;
  while(left<=right){  // 考虑一下这为什么要取等？
    Position center = (left+right)/2;  //先找中间值 
    if(L->Data[center] < X){     //比中间值大，X 在右半边 
      left = center+1;
    }else if(X < L->Data[center]){   //比中间值小，X 在左半边 
      right = center-1;
    }else  //找到了，直接返回 
      return center;
  }
  return NotFound;
}

#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        // 如果找到元素，则返回元素的索引
        if (arr[mid] == x)
            return mid;
        // 如果待查找的值小于中间元素，则在左半部分继续查找
        if (arr[mid] > x)
            r = mid - 1;
        // 如果待查找的值大于中间元素，则在右半部分继续查找
        else
            l = mid + 1;
    }
    // 如果未找到元素，则返回-1
    return -1;
}
int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        printf("元素不在数组中");
    else
        printf("元素在数组中的索引为 %d", result);
    return 0;
}