最大子段和(分治法)

来源:http://www.cnblogs.com/chen9510/archive/2016/09/30/5925021.html
-Advertisement-
Play Games

題目:輸入n個數,求最大的連續子段和,並輸出子段的起點下標和終點下標; 思路:分治法; 代碼如下: ...


題目:輸入n個數,求最大的連續子段和,並輸出子段的起點下標和終點下標;

思路:分治法;

 

代碼如下:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#define N 1000005
using namespace std;
int a[1005];

int calc(int s,int e,int &l,int &r)
{
    int l1,l2,l3,r1,r2,r3;
    ///if(s==e)  return a[s]>0?a[s]:0;
    if(s==e)
    {
        if(a[s]>0)
        {
            l=s;
            r=s;
            return a[s];
        }
        else return 0;
    }
    int mid=(s+e)>>1;
    int sum1=calc(s,mid,l1,r1);
    int sum2=calc(mid+1,e,l2,r2);
    int sl=0,sr=0,t=0;
    for(int i=mid; i>=s; i--)
    {
        t+=a[i];
        if(sl<t) sl=t,l3=i;
    }
    t=0;
    for(int i=mid+1; i<=e; i++)
    {
        t+=a[i];
        if(sr<t) sr=t,r=i,r3=i;
    }
    int ss=sl+sr;
    l=l3,r=r3;
    if(ss<=sum1) ss=sum1,l=l1,r=r1;
    if(ss<=sum2) ss=sum2,l=l2,r=r2;
    return ss;
}

int main()
{
    int n;
    while(1)
    {
        printf("輸入數列長度:");
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        int l=1,r=1;
        int sum=calc(1,n,l,r);
        if(sum>0)
        {
            cout<<"最大子段和:"<<sum<<endl;
            cout<<"起點和終點:"<<l<<" "<<r<<endl;
        }
        else
        {
            cout<<"最大子段和:"<<sum<<endl;
            cout<<"無起點和終點!"<<endl;
        }
        cout<<endl;
    }
    return 0;
}

 運行截圖:

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1. Comparator 和 Comparable 相同的地方他們都是java的一個介面, 並且是用來對自定義的class比較大小的,什麼是自定義class: 如 public class Person{ String name; int age }.當我們有這麼一個personList,裡面包含 ...
  • 物理地址 堆的物理地址分配對對象是不連續的。因此性能慢些。在GC的時候也要考慮到不連續的分配,所以有各種演算法。比如,標記 消除,複製,標記 壓縮,分代(即新生代使用複製演算法,老年代使用標記——壓縮) 棧使用的是數據結構中的棧,先進後出的原則,物理地址分配是連續的。所以性能快。 記憶體分別 堆因為是不連 ...
  • 異常 異常(Exception)是因為程式的例外、違例、出錯等情況而在正常控制流以外採取的行為,一般分為如下兩個階段: 1.異常發生:一個錯誤發生後被列印出來,稱為未處理異常,而預設的處理則是自動輸出一些調試信息並終止程式運行。 2.異常處理:通過代碼明確地處理異常,則程式不會終止運行,並增強程式的... ...
  • package com.gdh.backtext;import java.util.HashMap;import java.util.Map;import java.util.Map.Entry; public class BackText { String text; public BackTex ...
  • 函數重寫overwrite: 當子類提供了和父類同名的虛函數時,稱之為函數重寫,函數的返回值類 函數名 參數列表必須完全相同 名字隱藏namehide: 當子類提供了和父類同名的數據時 叫名字隱藏 函數重載: 同一個作用域中 函數名相同 參數列表不同的函數構成重載 多態 當父類型的指針(引用)指向子 ...
  • (更多內容請關註本人微信訂閱號:it_pupil) 你沒進錯,我們講的是Java的輸入輸出流。 概述 ➤ 可以從其中讀入一個位元組序列的對象稱作輸入流。(輸入流是一個對象,可以從這個對象中讀取一個位元組序列。) ➤ 可以向其中寫入一個位元組序列的對象稱作輸出流。 ➤ 讀入或者寫入的位元組序列當然有個來源地和 ...
  • 在PB實現支付寶當面付的功能,需要先在支付寶進行商戶簽約,並設置相關的公鑰信息(具體參考支付寶文檔)。 然後使用對應的私鑰文件對參數進RSAWithSha1前面計算。具體代碼如下: 其中wf_alipay_urlencode函數代碼如下: demo代碼詳見w_rsa窗體的SHA1WithRSA按鈕下 ...
  • 在學習qt過程中,遇到了編譯oracle驅動的問題,在開源協議下沒有編譯好的,那就只能自己來了 雖然網上已經有了很多這種文章 但是大多都用不了,攤手.jpg win7 (64bit) oracle 11g (r2) qt (5.60/5.70) 通過 qt oci源碼目錄 D:\Qt5.7.0\5. ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...