#include<iostream>
#include<stdio.h>
using namespace std;
int MaxSubsequenceSum(int a[],int n);
int main(){
//int a[6] = {-2, 11, -4, 13, -5, -2};
int a[8] = {4, -3, 5, -2, -1, 2, 6, -2};
printf("%d\n",MaxSubsequenceSum(a,8));
}
int MaxSubsequenceSum(int a[],int n){
int ThisSum, MaxSum;
MaxSum = 0;
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
ThisSum = 0;
for(int k = i; k <= j; k++){
ThisSum += a[k];
}
if(ThisSum > MaxSum){
MaxSum = ThisSum;
}
}
}
return MaxSum;
}
这是一种O(n^3)的解法,说实话,我是写不来这样高时间复杂度的算法,这个算法重复做了很多的无用的计算,强行将算法复杂化,经过简单的分析,直接可以求 ThisSum += a[k] 语句的次数,就能够得出它的时间复杂度:
请问经过简单分析,是怎么分析的。
我假设i=1,经过运算得出 最内层循环执行了(1+n)n/2 次,i=2时 最内层循环执行了(2+n)(n-1)/2次,i=3时,最内层循环执行了(3+n)(n-2)/2次……
因为 i的取值范围是0到N,所以 我尝试把上面的加起来,接下来就不会了,请求赐教,或者告诉我最后图片上的那个是怎么对到出来的