#include<iostream>
#include<cstdlib>
using namespace std;
int getmax(int array[],int length)
{
    int sum = 0;
    int max = 0;
    int startIndex = 0; //记录子数组的起始位置
    int endIndex = 0;   //记录子数组的终止位置
    int newStartIndex = 0;
    for (int i = 0; i < length; i++)    //遍历整个目标数组
    {
        if (max < 0)
        {
            max = array[i];
            newStartIndex = i;
        }
        else
        {
            max += array[i];
        }
        if (sum < max) //如果此时 sum < temp；
        {
            sum = max;
            startIndex = newStartIndex;
            endIndex = i;
        }
    }
    return max;
}

int getstartIndex(int array[],int length)
{
    int sum = 0;
    int max = 0;
    int startIndex = 0;
    int endIndex = 0;
    int newStartIndex = 0;
    for (int i = 0; i < length; i++)
    {
        if (max < 0)
        {
            max = array[i];
            newStartIndex = i;
        }
        else
        {
            max += array[i];
        }
        if (sum < max)
        {
            sum = max;
            startIndex = newStartIndex;
            endIndex = i;
        }
    }
    return startIndex;
}
int getendIndex(int array[],int length)
{
    int sum = 0;
    int max = 0;
    int startIndex = 0;
    int endIndex = 0;
    int newStartIndex = 0;
    for (int i = 0; i < length; i++)
    {
        if (max < 0)
        {
            max = array[i];
            newStartIndex = i;
        }
        else
        {
            max += array[i];
        }
        if (sum < max)
        {
            sum = max;
            startIndex = newStartIndex;
            endIndex = i;
        }
    }
    return endIndex;
}


int main()
{
    int array[]={-32,-10,33,-23,32,-12,41,-12,1,3,5,-98,70,-21,10,-9,61};
    int length=17;
    cout<<"最大子数组的和："<<getmax(array,length)<<endl;
    cout<<"最大子数组开始的下标："<<getstartIndex(array,length)<<endl;
    cout<<"最大子数组结束的下标："<<getendIndex(array,length)<<endl;
    system("pause");
    return 0;
}