#include<iostream>
#include<cstdlib>
using namespace std;
int getmax(int array[],int length)
{
    int sum = 0;    //记录当前连续子数组的最大和
    int max = 0;   //记录当前数组连续几个元素的和（当其值小于0时，重新对其赋值；【即：抛弃前面的所有元素】）
    int startIndex = 0; //记录子数组（和最大）的起始位置
    int endIndex = 0;   //记录子数组（和最大）的终止位置
    int newStartIndex = 0;  //记录子数组（和最大）的新的起始位置
    for (int i = 0; i < length; i++)    //遍历整个目标数组
    {
        if (max < 0)   //如果max < 0；则要对max重新赋值
        {
            max = array[i];    //对max重新赋值
            newStartIndex = i;  //暂时记录子数组（和最大）的新的起始位置（要看后续的sum 和 max是否发生交换）
        }
        else
        {
            max += array[i];   //如果max >= 0；则要继续将此时的数组元素(array[i])加入到max中
        }
        if (sum < max) //如果此时 sum < max；则表示此时的子数组和大于之前的子数组和
        {
            sum = max; //将大的子数组和max赋值给sum
            startIndex = newStartIndex; //子数组（和最大）的新的起始位置起作用了
            endIndex = i;   //子数组（和最大）的终止位置（只要发生交换就说明endIndex发生变化）
        }
    }
    return max;
}

int getstartIndex(int array[],int length)
{
    int sum = 0;    //记录当前连续子数组的最大和
    int max = 0;   //记录当前数组连续几个元素的和（当其值小于0时，重新对其赋值；【即：抛弃前面的所有元素】）
    int startIndex = 0; //记录子数组（和最大）的起始位置
    int endIndex = 0;   //记录子数组（和最大）的终止位置
    int newStartIndex = 0;  //记录子数组（和最大）的新的起始位置
    for (int i = 0; i < length; i++)    //遍历整个目标数组
    {
        if (max < 0)   //如果temp < 0；则要对temp重新赋值
        {
            max = array[i];    //对max重新赋值
            newStartIndex = i;  //暂时记录子数组（和最大）的新的起始位置（要看后续的sum 和 max是否发生交换）
        }
        else
        {
            max += array[i];   //如果max >= 0；则要继续将此时的数组元素(array[i])加入到max中
        }
        if (sum < max) //如果此时 sum < max；则表示此时的子数组和大于之前的子数组和
        {
            sum = max; //将大的子数组和max赋值给sum
            startIndex = newStartIndex; //子数组（和最大）的新的起始位置起作用了
            endIndex = i;   //子数组（和最大）的终止位置（只要发生交换就说明endIndex发生变化）
        }
    }
    return startIndex;
}
int getendIndex(int array[],int length)
{
    int sum = 0;    //记录当前连续子数组的最大和
    int max = 0;   //记录当前数组连续几个元素的和（当其值小于0时，重新对其赋值；【即：抛弃前面的所有元素】）
    int startIndex = 0; //记录子数组（和最大）的起始位置
    int endIndex = 0;   //记录子数组（和最大）的终止位置
    int newStartIndex = 0;  //记录子数组（和最大）的新的起始位置
    for (int i = 0; i < length; i++)    //遍历整个目标数组
    {
        if (max < 0)   //如果max < 0；则要对max重新赋值
        {
            max = array[i];    //对max重新赋值
            newStartIndex = i;  //暂时记录子数组（和最大）的新的起始位置（要看后续的sum 和 max是否发生交换）
        }
        else
        {
            max += array[i];   //如果max >= 0；则要继续将此时的数组元素(array[i])加入到max中
        }
        if (sum < max) //如果此时 sum < max；则表示此时的子数组和大于之前的子数组和
        {
            sum = max; //将大的子数组和max赋值给sum
            startIndex = newStartIndex; //子数组（和最大）的新的起始位置起作用了
            endIndex = i;   //子数组（和最大）的终止位置（只要发生交换就说明endIndex发生变化）
        }
    }
    return endIndex;
}


int main()
{
    int length,i=0;
    cout<<"请输入个数：";
    cin>>length;
    cout<<"请输入数组：";
    int array[1000]={0};
    for(i=0;i<length;i++)
    {
        cin>>array[i];
    }
        cout<<"最大子数组的和为："<<getmax(array,length)<<endl;
    cout<<"最大子数组起始下标："<<getstartIndex(array,length)<<endl;
    cout<<"最大子数组结束下标："<<getendIndex(array,length)<<endl;
    system("pause");
    return 0;
}