[数据结构]一些常见的算法思想

1,分治思想
计算输入向量中任何连续子向量中的最大和。
[31,-41,59,26,-53,58,97,-93,-23,84]
直接算法：

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
 
  1. maxsofar=0  
  2. for i = [0,n)  
  3.     sum = 0  
  4.     for j = [i, n)  
  5.         sum += x[j]  
  6.         maxsofar=max(maxsofar,sum)  


分治思想：
将向量分解为两个子向量，求解每个向量最大和，或者最大值在子向量a和子向量b的边界处

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
 
  1. float maxsum3(l,u)  
  2.     if(l > u)  
  3.         return 0  
  4.     if(l == u)  
  5.         return max(0,x[1])  
  6.     m = (l + u)/2  
  7.     lmax = sum = 0  
  8.     for(i = m; i>=l;i--)  
  9.         sum += x[i]  
  10.         lmax=max(lmax,sum)  
  11.     rmax=sum=0  
  12.     for i = (m,u]  
  13.         sum+=x[i]  
  14.         rmax=max(rmax,sum)  
  15.     return max(lmax+rmax,maxsum3(l,m),maxsum3(m+1,u))  

最初调用如下： answer=maxsum3(0,n-1)
将n向量分解为n-1和向量n

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
 
    1. maxsofar=0  
    2. maxendinghere=0  
    3. for i = [0,n)  
    4.     maxendinghere=max(maxendinghere+x[i],0)  
    5.     maxsofar=max(maxendinghere,maxsofar)  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zhiliao112/p/4237180.html