LeetCode-Maximum Subaray最大連続サブシーケンスと(動的計画)

3946 ワード
Algorithmsアルゴリズム OJ LeetCode
古典的な問題-最大連続サブシーケンスと

Maximum Subarray

 
Total Accepted: 15186 
Total Submissions: 46442 My Submissions
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array  [−2,1,−3,4,−1,2,1,−5,4] , the contiguous subarray  [4,−1,2,1]  has the largest sum =  6 .
click to show more practice.
More practice:
If you have figured out the O(n) solution, try coding another solution 
using the divide and conquer approach, which is more subtle.
Have you been asked this question in an interview? 

問題の分析と解題の構想:


古典的な最大連続サブシーケンスと問題.重要なのは問題を分析することです
まず、1つのシーケンスに複数の連続するサブシーケンスとが存在する可能性があることを考える. 
次に、各サブシーケンスとをどのように見つけますか.
最後に最大値を返します.
まず、第1の要素を1つのサブシーケンスS 1とし、その後の要素jがS 1に属していないと判断し、要素jにS 1の和を加えた後、元の値より大きいか否かを判断する.
sum(S 1,j)>sum(S 1);するとjをS 1に追加し、その後スキャンを継続する.
sum(S 1,j)最後に、最大のサブシーケンスを返します.
最後に、配列内の要素はすべてまたは部分的に負数、0、正数である可能性があることを考えます.溢れ出すかどうか注意してください.
また、「最大の連続サブシーケンスと両側の要素は必ず正である」という言葉は間違っており、負の数が2つの比較的大きなシーケンスを接続して総和を最大にすることができるか、シーケンスの中ですべて負の数ではない.

プログラムのソースコードと分析：


Javaソース:データA内の要素値は変更されません.
//     O（n），     O（1）
public class Solution {
    public static int maxSubArray(int[] A) {
        int maxSum = Integer.MIN_VALUE;
        int curMaxSum = 0;
        for (int i = 0; i < A.length; ++i) {
            curMaxSum = Math.max(curMaxSum + A[i], A[i]);
            maxSum = Math.max(curMaxSum, maxSum);
        }
        return maxSum;
    }
}

コメント:
1.Note 1:これはコードの鍵です.
まず、1つの要素(1つの要素を含むサブシーケンスと見なすこともできる)が前のサブシーケンスに属するかどうかを判断し、temp*A[i]>=0のような積を考慮するのではなく、前の加算と元より大きいかどうかを見るべきである.これは無視しても負数になるので、一緒に加えるべきではありません!問題の意味をはっきり分析することが最も重要だ.
2.提出したコードが開くのは簡単できれいで、これはすべて修正されたものです.自分で問題をする時更に論理と問題の分析を重視すべきで、コードworkを待ってからコードを最適化して、書くのが少しきれいです.
3.最大連続サブシーケンス和の動的計画における状態は、現在の状態iの最大サブシーケンス和である.currentMaximumSum(i) = Max (currentMaximumSum(i-1) , currentMaximumSum(i-1) + A[i]). また、状態iが更新される度の最大サブシーケンス和は、従来の計算過程におけるすべての最大サブシーケンスの和の最大値が更新される.
付録:
原題住所:https://oj.leetcode.com/problems/maximum-subarray/
独立して走ることができるソースコードとサンプル:
ソース:
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;

public class MaximumSubarray {

    public static void main(String args[]) throws IOException {
        FileInputStream fis = new FileInputStream("input.txt");
        System.setIn(fis);
        // PrintStream ps = new PrintStream(new FileOutputStream("output.txt"));
        // System.setOut(ps);
        Scanner sc = new Scanner(System.in);
        String line;
        int lineNo = 1;
        while (sc.hasNextLine()) {
            line = sc.nextLine().trim();
            String strs[] = line.split(",");
            System.out.println(line);
            int list[] = new int[strs.length];
            for (int i = 0; i < strs.length; ++i) {
                list[i] = Integer.valueOf(strs[i].trim());
            }
            System.out.println((lineNo++) + " : " + maxSubArray(list));
        }
        sc.close();
    }

    public static int maxSubArray(int[] A) {
        int maxSum = Integer.MIN_VALUE;
        int curMaxSum = 0;
        for (int i = 0; i < A.length; ++i) {
            curMaxSum = Math.max(curMaxSum + A[i], A[i]);
            maxSum = Math.max(curMaxSum, maxSum);
        }
        return maxSum;
    }
}

input.txtサンプル:
-1,-2 2,3 -2,-1 -2,0,1 1,0,-2 0,1,-2 -2,1,0 0, 0, -2, 0 ,0 0, 0, 2 -2, 1, -3, 4, -1, 2, 1, -5, 4 -2, 1, -3, 4, -1, 2
ノード、エクスプレス、nodemailer、およびTailWindCSSとの接触フォームを作成します.
JavaScriptのヒープ、スタック、リファレンス、および値の簡単なガイド