Skip to content
Abies的笔记
数据结构基础
最大连续和子数组

最大连续和子数组

约 1 分钟阅读 · 336 字 · 次浏览

:smiley:Class Two

最大和连续子数组

  1. 暴力法:O(n^3)
  2. 暴力法优化:O(n^2) 确定 i 后,遍历 j 时即完成求和
int MaxSum(int a[],int len) {
    int nsum,maxsum;
    maxsum=0;
    for (int i=0;i<len;i++) {
        nsum=0;
        for (int j=1;j<len;j++) {
            nsum+=a[j]; //j右移时加
            if (nsum>maxsum) maxsum=nsum;
        }
    }
    return maxsum;
}
  1. 搜索区间+前缀和:O(n^2)
  2. 分治法:O(nlogn) 分成左半边,右半边,中间
int MaxSum(int l,int r) {
    if (l==r) return a[l]; //返回条件

    int mid=(l+r)>>1;
    int max1=MaxSum(l,mid); //计算左半边
    int max2=MaxSUm(mid,r); //计算右半边

    int max3,lmax=0,rmax=0,sum=0;
    for (int i=mid;i>=l;i--) {
        sum+=a[i];
        lmax=max(lmax,sum);
    }
    sum=0;
    for (int i=mid+a;i<=r;i++) {
        sum+=a[i];
        ramx=max(ramx,sum);
    }
    max3=lmax+rmax;

    return max(max1,max2,max3);
}
  1. 线性 dp:O(n) 状态转移方程:dp[i]=max(dp[i-1]+a[i],a[i])
  2. 扫描法:O(n)
int MaxSum() {
    int res=-INF,sum=0;
    for (int i=1;i<=len;i++) {
        if (sum<0) sum=a[i];
        else sum+=a[i];

        res=max(res,sum);
    }
    return res;
}

链表(略)

HW2

If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then which of the following data structures is the most efficient? A.doubly linked list B.singly linked circular list C.doubly linked circular list with a dummy head node D.sequential list 访问随机节点:相同 最后位置:循环链表可通过虚拟头结点后移一位直接找到最后一位

时间复杂度堆栈和队列