求最大子序列和（笔试中经常遇到的问题）

#include <iostream>
using namespace std;
/****************************************************************************************/
/*第一种方法，容易想到，时间复杂度为O(n*n) **************************************/
/*传入一数组首地址和数组元素个数，传出最大子序列和，并同时打印输出下标范围*/
/****************************************************************************************/
int Max1(int *data, int n)
{
    int i,j,left = 0, right = 0;
    int result = 0;
    int max = data[0];
    for (i = 0; i < n; i ++)
    {
        result = 0;
        for (j = i; j < n; j ++)
        {
            result += data[j];
            if (result > max)
            {
                max = result;
                left = i;
                right = j;
            }
            
        }
    }
    cout<<"left = "<<left<<", right = "<<right<<endl;
    return max;
   
}
/****************************************************************************************/
/*第二种方法，不容易想到，时间复杂度为O(n) **************************************/
/*传入一数组首地址和数组元素个数，传出最大子序列和，并同时打印输出下标范围*/
/****************************************************************************************/
int Max2(int *data, int n)
{
    int max1 = 0, max2 = 0;
    int temp = 0;
    int left = 0, right = 0;
    int lt = 0;
    for (int i = 0; i < n; i ++)
    {
        temp = (max1 + data[i]);   
        if (temp > 0)
        {
            max1 = temp;
        }
        else
        {   
            lt = i + 1;
            max1 = 0;
        }
       
        if (max1 > max2)
        {
            left = lt;
            right = i;
            max2 = max1;
        }
    }
    if (left == 0 && right == 0 && max2 == 0 && data[0] != 0)
    {
        max2 = data[0];
        for (int j = 1; j < n; j ++)
        {
            if (data[j] > max2)
            {
                max2 = data[j];
                right = j;
                left = j;
            }
        }
    }
    cout<<"left = "<<left<<", right = "<<right<<endl;
    return max2;
}

int main()
{
    int arr[10]={-2,-20,-1,-20,2,90,-70,20,50,-80};
    cout<<"First way:"<<endl;
    cout<<"The largest result is :"<<Max1(arr,9)<<endl<<endl;

    cout<<"Second way:"<<endl;
    cout<<"The largest result is :"<<Max2(arr,9)<<endl;
    return 0;
}
运行结果如下：