第1节 基本概念

1.什么是数据结构？

数据之间的关系是数据结构。

举例：

2.什么是算法？

有了数据结构，我还要对其进行遍历或查找，或删除或插入或修改。
这个处理过程就是算法。
算法就是处理数据关系的方法。
数据之间有很多关系，一个数据关系处理方法也有很多。
我们希望采用最好的那个算法。
我们通过它们的时间复杂度和空间复杂度来找出最适用的算法。

时间复杂度

时间复杂度就是算法语句的执行次数。
通常有这些1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!。
比如

for(i=1;i<=n;++i)
{
    for(j=1;j<=n;++j)
    {
        c[i][j]=0;//该步骤属于基本操作执行次数：n的平方次
        for(k=1;k<=n;++k)
            c[i][j]+=a[i][k]*b[k][j];//该步骤属于基本操作执行次数：n的三次方次
    }
}

空间复杂度

暂时不关心。
主要包括动态分配的空间，以及递归栈所需的空间等。

3.作业

输入一组整数，求出这组数字子序列和中的最大值，只要求出最大子序列的和，不必求出最大值对应的序列。

最大子序列和：整数序列A1， A2，... An （可能有负数），求A1_{An的一个子序列Ai}Aj，使得Ai到Aj的和最大。

例如：
序列：-2, 11, -4, 13, -5, 2, -5, -3, 12, -9，则最大子序列和为21。
序列：0, -3, 6, 8, -20, 21, 8, -9, 10, -1, 3, 6, 5，则最大子序列和为43。

解答之一：

"use strict"
const Max_Son= function(arr){
    let max_sum = 0;
    let len = arr.length;
    let i,j;
    for(i=0; i< len; i++){
        let sum = 0;
        for(j=i; j<len; j++){
            sum = sum + arr[j];
            if(sum > max_sum){
                max_sum = sum;
            }    
        }
    }
    return max_sum;
}

console.log(Max_Son([-2, 11, -4, 13, -5, 2, -5, -3, 12, -9]));
console.log(Max_Son([0, -3, 6, 8, -20, 21, 8, -9, 10, -1, 3, 6, 5]));

题目变异：
求整数数组中求最大连续子序列之和，并且记录开始和结束位置。
该题目各种时间复杂度的算法。