leetcode算法题53：
求解最大连续子序列和
https://leetcode.com/problems/maximum-subarray/?tab=Description

题目描述：找出一个序列的连续子序列元素相加最大值

解题思路：使用动态规划的思想，从左到右扫描序列，将新节点的值和之前的连续序列节点和相加与之前的连续节点和作比较，更大者作为最大值，如果相加后小于0,则将和设为0继续往后扫描，即舍弃之前节点。
注意点：最开始初始化sum值时应设为系统表示最小值，预防序列内节点均为负产生错误结果

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxans = -1*(sys.maxint)-1
        sum = 0
        for index in range(len(nums)):
            sum = sum + nums[index]
            maxans = max(sum, maxans)
            if sum<0:
                sum = 0
        return maxans

准备开始刷leetcode上的算法题，并对相关内容进行记录
今天记录的是leetcode上编号为1的题目TwoSum
leetcode链接如下：https://leetcode.com/problems/two-sum/

题目描述：给定一个只包含整数的数组，返回由数组中两个数相加之和为target的下标，假定该数组中有且只有一个解，且每个元素只能使用一次
举例： nums=[2, 7, 11, 15], target = 9,
返回[0,1]
解题思路：
思路一：暴力解法，两次循环，复杂度n^2，不能通过
思路二：新建一个字典，将元素放进去，查找target-x是否在字典中，复杂度n
以下给出了思路二的解法

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        ret = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    ret = [i, j]
                    return ret
        return ret

1、k折交叉验证 中k取值多少有什么关系（ML19.6)，bias，variance是什么(ML4.3)？

  答：一般来说，对于机器学习任务，都会将数据集分为训练数据、验证数据。然而如何对数据集划分却要考虑很多方面的问题，如划分比例、数据成分统计特性等。这里提问中的K主要指的是划分比例的问题范畴。
  首先这里的K指的是将数据等分为k份，然后将其中的k-1份作为训练数据，一份做测试数据。
  然后，在对数据进行划分时得确保训练集和验证集的数据分布相同，即确保其统计特性一致。
  我们可以想象一下，一般来说，k越大训练数据越多，验证数据越少，即模型训练越充分,但是验证结果就越不精准，极端情况下k和样本数相同，即只留一个验证数据，leave one out。那样验证结果就很不精确了。所以k折交叉验证中验证结果好坏随着k增大而增大，然后再随着k增大而减小。
  在k折交叉验证中还有一种常见的方法就是，随机挑选出k-1份当训练、下次再随机挑选出k-1个做训练，这样经过多次k-1份的训练从而增加模型的效果。
  那么bias、variance又是什么呢，与此相对应的还有一个概念叫error，error指的是模型预测结果与实际值之间的误差，通常
error=bias+variance 。
Bias反映的是模型在样本上的输出与真实值之间的误差，即模型本身的精准度，Variance反映的是模型每一次输出结果与模型输出期望之间的误差，即模型的稳定性。

2、分类模型和回归模型的区别？（ML2.6）

  1）首先分类模型和回归模型都是有监督学习
  2）从预测结果上来看，分类模型的结果是离散值，回归模型是连续值
  3）从训练数据上看，分类模型的标记是离散值，回归模型的标记是连续值
  4）一定程度上讲，分类和回归是可以相互转化的

3、分类模型可以做回归分析吗？反过来可以吗？ML2.6

  分类模型可以做回归分析，回归模型也可以做分类
  1）对于分类模型，如果把分类标签划分的足够多，足够细，即可类似转化为回归模型
  2）对于回归模型，只需要将回归预测结果划分到一定范围，属于该范围的回归值就划分到该分类区，通过这种方法就可以将回归模型转化为分类模型。

目的

第一部分是之前搜集的一些题目，所以这次的标题就为《二》咯
这一部分主要是讲解线性回归、逻辑回归的原理和一些常见校招题。

Logistic回归：
　　Logistic是用来分类的，是一种线性分类器，需要注意的地方有：
　　1. logistic函数表达式为：
　　


　　其导数形式为：
　　
　　2. logsitc回归方法主要是用最大似然估计来学习的，所以单个样本的后验概率为：
　　
　　到整个样本的后验概率：
　　
　　其中：
　　
　　通过对数进一步化简为：
　　
　　3. 其实它的loss function为-l(θ)，因此我们需使loss function最小，可采用梯度下降法得到。梯度下降法公式为:
　　
　　
　　Logistic回归优点：
　　1、实现简单；
　　2、分类时计算量非常小，速度很快，存储资源低；
　　缺点：
　　1、容易欠拟合，一般准确度不太高
　　2、只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；

　　线性回归：
　　线性回归才是真正用于回归的，而不像logistic回归是用于分类，其基本思想是用梯度下降法对最小二乘法形式的误差函数进行优化，当然也可以用normal equation直接求得参数的解，结果为：
　　
　　而在LWLR（局部加权线性回归）中，参数的计算表达式为:
　　
　　因为此时优化的是：
　　
　　由此可见LWLR与LR不同，LWLR是一个非参数模型，因为每次进行回归计算都要遍历训练样本至少一次。
　　线性回归优点：
　　实现简单，计算简单；
　　缺点：
　　不能拟合非线性数据；

参考资料：
[1] http://blog.sciencenet.cn/blog-520608-745856.html