首页 > 其他分享 >循环数组的最大子段和

循环数组的最大子段和

时间:2023-05-31 15:02:23浏览次数:45  
标签:最大 子段 int LL 循环 数组 ans


题目:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050

 

题意:给定一个长度为50000的数组,求它的循环数组的最大子段和。


分析:本题与普通的最大子段和问题不同的是,最大子段和可以是首尾相接的情况,即可以循环。那么这个题目的最

     大子段和有两种情况


    (1)正常数组中间的某一段和最大。这个可以通过普通的最大子段和问题求出。

    (2)此数组首尾相接的某一段和最大。这种情况是由于数组中间某段和为负值,且绝对值很大导致的,那么我

        们只需要把中间的和为负值且绝对值最大的这一段序列求出,用总的和减去它就行了。


     即,先对原数组求最大子段和,得到ans1,然后把数组中所有元素符号取反,再求最大子段和,得到ans2,

     原数组的所有元素和为ans,那么最终答案就是 max(ans1, ans + ans2)


代码:

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

using namespace std;
typedef long long LL;
const int N = 50005;

int a[N];

LL Work(int a[], int n)
{
    LL ans = 0;
    LL tmp = 0;
    for(int i=0; i<n; i++)
    {
        if(tmp < 0) tmp = a[i];
        else tmp += a[i];
        ans = max(ans, tmp);
    }
    return ans;
}

int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        LL ans = 0;
        for(int i=0; i<n; i++)
        {
            scanf("%d", &a[i]);
            ans += a[i];
        }
        LL ans1 = Work(a, n);
        for(int i=0; i<n; i++)
            a[i] = -a[i];
        LL ans2 = Work(a, n);
        ans = max(ans + ans2, ans1);
        printf("%I64d\n", ans);
    }
    return 0;
}

 


标签:最大,子段,int,LL,循环,数组,ans
From: https://blog.51cto.com/u_16146153/6386939

相关文章

  • Java中常见转换-数组与list互转、驼峰下划线互转、Map转Map、List转Map、进制转换的多
    场景Java中数组与List互转的几种方式数组转List1、最简单的方式,Arrays.asList(array);创建的是不可变列表,不能删除和新增元素String[]array=newString[]{"a","b"};List<String>stringList=Arrays.asList(array);System.out.println(strin......
  • GO分支循环
    (文章目录)单分支ifcondition{代码块}if5>2{fmt.Println("5greaterthan2")}==注意==:Go语言中,花括号一定要跟着if、for、func等行的最后,否则语法出错。这其实就是为了解决C风格、Java风格之争。condition必须是一个bool类型,在Go中,不能使用其他类型等效......
  • 1439. 有序矩阵中的第 k 个最小数组和
    给你一个m *n的矩阵mat,以及一个整数k,矩阵中的每一行都以非递减的顺序排列。你可以从每一行中选出1个元素形成一个数组。返回所有可能数组中的第k个最小数组和。来源:力扣(LeetCode)链接:https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-so......
  • 二分法应用——搜索旋转数组,以前一直在纠结a[0],a[-1],a[mid], target三者关系,其实最
    62·搜索旋转排序数组  描述给定一个有序数组,但是数组以某个元素作为支点进行了旋转(比如,0124567可能成为4567012)。给定一个目标值target进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1。你可以假设数组中不存在重复的元素。背完这套刷题模板,真......
  • 多维数组遍历
    #include<stdio.h>intmain(){intarr[][3]={{1,2},{3,4,5}};inti=0;intj=0;intlen=0;for(i=0;i<2;i++){for(j=0;j<3;j++){printf("arr[%d][%d]:%d",i,j,arr[i][j]);}prin......
  • heapq 对有序的数组列表进行整体排序
     """功能:实现对有序的多个数组整体排序,获取topk个最小元素"""fromheapqimport*defheap_sort(arr,top_k):q=[]foriinrange(len(arr)):heappush(q,(arr[i][0],i,0))result=[]forkinrange(top_k):ifq:......
  • 【shell】ubuntu循环输出当前日期
    1、场景  我想实时输出当前系统时间,对比日志之间的时间差 2、方法#!/bin/bashwhile(true)doecho$(date+%F%n%T)sleep1done 3、date命令参数~$date--helpUsage:date[OPTION]...[+FORMAT]or:date[-u|--utc|--universal][MMDDhhmm[[CC]YY][......
  • Gym - 101174F[(DSU)+树状数组]
    题目链接:https://vjudge.net/problem/Gym-101174F 解题思路:其实这题不同启发式合并也可以做,对rank排个序,然后在做个dfs序,把rank值小的先插入树状数组中更新,然后对每个节点查询它的dfs序的区间和就好了。对于DSU来说就更加无脑了,本来就是"暴力",所以我们直接DSU再加一个树状数组维......
  • python二维数组切片
    随堂测试这道题错了,于是怒而发blog,是分割维度的标识符,如果对象是二维数组,则切片应当是x[,]的形式,逗号之前和之后分别表示对象的第0个维度和第1个维度;如果对象是三维数组,则切片应当是x[,,],里面有两个逗号,分割出三个间隔,三个间隔的前、中和后分别表示对象的第0、1、2个维度。每个......
  • wukong引擎源码分析之索引——part 1 倒排列表本质是有序数组存储
    searcher.IndexDocument(0,types.DocumentIndexData{Content:"此次百度收购将成中国互联网最大并购"})engine.go中的源码实现://将文档加入索引////输入参数://docId标识文档编号,必须唯一//data见DocumentIndexData注释////注意://1.这个函数是线程安全......