Properties of the algorithm

• Infinity
• Availability
• certainty
• Terminality

-Input and Output

Description of the algorithm

• Natural Language Description
• Natural Language Plus Mathematical Formula
• Programming Language Description

-Pseudo Code Description

Common design pattern

• Enumeration Method

  Enumerate the possibilities based on the specific problem to select useful information or solutions to the problem.This method takes advantage of the speed advantage of the computer and is very effective in solving problems.

• Greedy

  Make a partial solution as much as possible based on the information of the problem, and gradually expand to a complete solution based on the partial solution.When solving complex problems, this approach may not lead to the best solution.

• Divide and Conquer

  The complex problem is decomposed into relatively simple subproblems and solved separately. The solution of the original problem is obtained by combining the solutions of the starting subproblems.

• Backtracking (Search)

  It refers specifically to solving by means of exploration.If the problem is complex and there is no clear solution path, it may need to be solved step by step, and each step may have multiple choices.In this case, only heuristic methods can be used to choose a possible direction based on the actual situation. When the later direction of solution cannot continue, you need to go back to the previous step and choose a solution path, which becomes backtracking.

• Dynamic programming method

  In some complex cases, problem solving is difficult to proceed directly, so information needs to be accumulated in the previous steps, and the best known solution path can be selected dynamically in the subsequent steps based on the known information (and information may be accumulated further).

• Branch and Bound Method

It can be seen as an improved form of the search method. If you can get some information during the search process to determine that some of the possible choices are not really useful, you can delete them as early as possible to reduce the solving space and speed up the problem solving process.

Calculation of operation time

General Rules

Rule 1 - for Loop

The run time of a for loop is at most the run time of those statements within the for loop multiplied by the number of iterations.

Rule 2 - Nested for loop

Analyze these cycles from inside out.The total run time of some statements within a set of nested loops is the product of the run time of the statement multiplied by the size of all for loops in the set
For example, the following program fragment is O(n2):

for(i = 0;i < n; i++){
    for(j = 0;j < n; j++){
        k++;
    }
}

Rule 3 - Sequential Statements

The actual sum of the run of each statement is sufficient.
n and n2 add to n2

Rule 4 - if/else statements

if(condition) s1
else s2

An if/else statement never runs longer than the judged run time plus the total run time for longer runs in s1 and s2.

The basic strategy for analysis is to work from within to outside.If there are method calls, they are analyzed first.

Maximum Subsequence and Problem

//Layer 1 loop controls first digit position
//Layer 2 Loop Control Tail Number Position
//Layer 3 loop adds numbers from start to end after the generation
//Complexity: n^3
public static int maxSubSum1(int[] a){
    int maxSum = 0;
    for(int i = 0; i < a.length; i++){

        for (int j = i; j < a.length; j++){

            int thisSum = 0;

            for(int k = i; k <= j; k++) thisSum += a[k];
            if (thisSum > maxSum) maxSum = thisSum;

        }

    }
    return maxSum;
}

//Layer 1 loop controls first digit position
//Layer 2 Loop Control Tail Number Position
//1,2 Two methods differ:
// 1. Subsequence generated by algorithm 1 is calculated from beginning to end
// 2.Algorithm 2 stores the last calculation result and adds the next trailing number as a new subsequence when the first loop is fixed.
//Complexity: n^2
public static int maxSubSum2(int[] a){

    int maxSum = 0;

    for(int i = 0; i < a.length; i++){

        int thisSum = 0;
        for (int j = i; j < a.length; j++){


             thisSum += a[j];
            if (thisSum > maxSum) maxSum = thisSum;

        }

    }
    return maxSum;
}

//Divide and conquer complexity nlogn
private static int maxSumRec(int[] a, int left, int right){

    if (left == right){
        if (a[left] > 0) return a[left];
        else return 0;
    }

    int center = (left + right) / 2;

    int maxLeftSum = maxSumRec(a, left, center);
    int maxRightSum = maxSumRec(a, center + 1, right);

    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for (int i = center; i>=left; i--){
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum;
    }
    int maxRightBorderSum = 0, rightBorderSum = 0;
    for (int i = center + 1; i <= right; i++){
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum;
    }
    System.out.println(maxLeftBorderSum+","+maxRightBorderSum);
    return max3(maxLeftBorderSum,maxRightBorderSum,maxLeftBorderSum+maxRightBorderSum);
}
private static int max3(int num1, int num2, int num3){
    int max = num1 > num2 ? num1 : num2;
    max = max >num3 ? max :num3;
    return max;
}
//1,2 algorithm optimization, the terminal subsequence of any critical negative sequence cannot be prefixed
public static int maxSubSum4(int[] a){
    int maxSum = 0,thisSum = 0;
    for(int j = 0; j < a.length; j++){
        thisSum += a[j];
        if (thisSum > maxSum){
            maxSum = thisSum;
        }
        else if(thisSum < 0){
            thisSum = 0;
        }
    }
    return maxSum;
}