题目描述

Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For

example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

输入

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

输出

For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

样例

输入样例

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

输出样例

Case 1:
14 1 4

Case 2:
7 1 6

---

题目大意就是输出最大的子序之和，并且输出对应子序列的开始和结束下标

AC代码

#include <iostream>
#include<stdio.h>

using namespace std;

int input_ans[100008], start_index, end_index ;

void output_ans(int sum,int i){

    cout << "Case " << i << ":" << endl;

    cout << sum << " " << start_index << " " << end_index << endl;
}

int main()
{
    int t , n ;

    ios::sync_with_stdio(0);
    cin >>t;


    for(int i = 1 ; i <= t ; i ++){
        cin >> n ;

        for(int j = 1 ; j <= n ; j ++){
            cin >> input_ans[j];

        }


        int local_sum = input_ans[1], temp_start = 1;
        start_index = 1 ;
        end_index = 1;

        for(int j = 2 ; j <= n ; j ++ ){
            if(input_ans[j - 1] >= 0){
                input_ans[j] += input_ans[j - 1];
            }
            else{
                temp_start = j;
            }

            if(input_ans[j] > local_sum){
                local_sum = input_ans[j];
                start_index = temp_start;
                end_index = j;
            }
        }


        output_ans(local_sum,i);
        if(i != t){
            cout << endl;
        }
    }

    return 0;
}

代码解释

这道题属于DP算法的入门题目

说实话，感觉这个题没那么简单，一开始没想到答案

开始的思路是，判断全正、全负和有负有正，然后根据最大值的位置和正数开始的位置去判断

看过别人的题解后发现，自己没有从题目的根本出发，找到真正解题的那个点。

改题解题的点其实就两个

• 判断输入的值的正负性

  • 只要前面一个大于0，就加上去（有条件的前缀和）
  • 如果小于0，记录为开始的位置

• 判断当前值与最大值的关系

  • 赋值最大值
  • 开始下标为——小于0时记录的下标
  • 结束下标为——当前下标

最后输出即可。

判断正负性

循环从下标为2的位置开始，判断前一个的元素是否大于0

• 是，则加入当前元素中

  将前面所有大于0的和都存入当前数组位置，便于下次计算

  • 全正：每一位都相加，最后一位就是子序列最大和
  • 全负：没有一位相加，开始和结束下标都是默认的1
  • 有负有正：只有大于0的数才相加

• 否，则记录下标

  若开始出现小于0的位置，则记录当前的下标。

  但此时并不确定结束的位置在哪里，只能确定开始的位置

  • 全正：不会出现开始下标，默认为1
  • 全负：下标一直被更替直到最后一位
  • 有负有正：只有小于0的数才会被记录下来

为什么需要判断元素是否大于0？

因为题目要求最大子序列和，只要加的数字不为负数，就可能出现最大子序列和

判断当前值与最大值关系

对从下标为2开始的每一位进行判断，对应的值与local_sum的大小关系

local_sum：默认初始值为数组第一位

大于

若当前的子序列和大于local_sum，则将local_sum的值更新为当前最大的子序列值

并记录当前的开始下标和结束下标

• 开始下标为前面所判断所得的temp_start

全正：temp_start为默认的1（因此，开始的下标也为1）特别注意这个默认值1

全负：虽然对于每一个小于0的数都进行了保留，但是并不会作为输出开始的下标——start_index，因为题目所要求的为最大子序列和，如果全负，则只会找到最大的那一个位置，并且会被更替

如下图所示

有负有正：判断当前的子序列和是不是最大的，如果比之前记录的大

就将开始的下标指向为负数的位置，结束下标指向当前

最后输出即可。

可能会有的坑——为方便输出格式混用cout和printf……