最大子列和问题的算法复杂度分析，不懂是怎么求出来的

Question

#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，所以 我尝试把上面的加起来，接下来就不会了，请求赐教，或者告诉我最后图片上的那个是怎么对到出来的

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 这篇文章：算法：最大子列和问题 也许能够解决你的问题，你可以看下

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 以帮助更多的人 ^-^