Java實(shí)現(xiàn)求子數(shù)組和的最大值算法示例

發(fā)布時(shí)間：2020-10-15 09:12:42 來(lái)源：腳本之家閱讀：189 作者：yayun0516 欄目：編程語(yǔ)言

本文實(shí)例講述了Java實(shí)現(xiàn)求子數(shù)組和的最大值算法。分享給大家供大家參考，具體如下：

一般C和C++在算法實(shí)現(xiàn)中使用較多，下面我們通過(guò)java語(yǔ)言實(shí)現(xiàn)算法，更有親切感。

題目：

輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。
數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。
求所有子數(shù)組的和的最大值。
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，
因此輸出為該子數(shù)組的和18。

實(shí)現(xiàn)代碼：

package arrDemo;
public class MaxSub {
    public static void main(String[] args) {
        // TODO 自動(dòng)生成的方法存根
        findMaxSubArySum1();
    }
    public static void findMaxSubArySum1() {
        // sum為子數(shù)組的和
        int sum = 0;
        // max為子數(shù)組的最大和
        int max = 0;
        // 最大子數(shù)組的起始位置
        int startPos = 0;
        // 最大子數(shù)組的結(jié)束位置
        int endPos = 0;
        int[] array = { -1, 2, -3, 12, -5, -1, 9, -2 };
        for (int i = 0; i < array.length; i++) {
            sum += array[i];// 求和
            if (sum < 0) {// 如果當(dāng)前求得總和為負(fù)數(shù)的話，就將其清零，并且開(kāi)始位置從下一個(gè)位置開(kāi)始
                sum = 0;
                startPos = i + 1;
            }
            if (sum > max) {// 如果求得總和大于之前的最大值的話，就將sum賦值給max，同時(shí)記錄最后的位置
                max = sum;
                endPos = i + 1;
            }
        }
        System.out.println("億速云測(cè)試結(jié)果：");
        System.out.println("Max:" + max);
        System.out.println("startPos:" + startPos + ",endPos:" + (endPos - 1));
    }
}

運(yùn)行結(jié)果：

Java實(shí)現(xiàn)求子數(shù)組和的最大值算法示例

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

向AI問(wèn)一下細(xì)節(jié)

Java實(shí)現(xiàn)求子數(shù)組和的最大值算法示例

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽