やったいくつかの面白いアルゴリズムの問題(解法付き)

問題1:HZはたまに専門的な問題を持ってコンピュータ以外の学生をからかっている.今日のテストグループの会議が終わった後、彼はまた話をしました:古い1次元モードの識別の中で、いつも連続するサブベクトルの最大和を計算する必要があって、ベクトルがすべて正数の時、問題はとてもよく解決します.しかし、ベクトルに負の数が含まれている場合、ある負の数を含んで、隣の正の数が補うことを期待しますか?例えば,{6,−3,−2,7,−15,1,2,2},連続サブベクトルの最大和は8(0番目から3番目まで)である.配列をあげて、その最大連続サブシーケンスの和を返して、あなたは彼にだまされませんか?(サブベクトルの長さは少なくとも1)
解答:動的に計画して、すべての正の答えを列挙します

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        if not array:
            return 0

        dp = [array[0]]

        i = 1
        for num in array[1:]:
            if dp[i - 1] <= 0: #                               ，       ，        
                dp.append(num)
            else:
                dp.append(dp[i - 1] + num)
            i += 1

        return max(dp)

a =  Solution()
array = [6, -3, -2, 7, -15, 1, 2, 2]
b = a.FindGreatestSumOfSubArray(array)
print b

 
 
問題2:文字列(配列)abcdのすべての組合せをリストする可能性のあるスキーム
 
解答:遡及法、すべての状況をリストして、それからlua解法を探して次のようにします

local Solution = {
  local allsolution = {}
  local insertyouranswer = {"a","b","c","d"}
  function dfs(dep, vecNum)  --      
    if dep == #insertyouranswer then
      table.insert(allsolution,vecNum)  --           ，      
      return
    end
    
    for idx = dep ,#insertyouranswer do
        swap(insertyouranswer[dep],insertyouranswer[idx])
        dfs(dep+1,insertyouranswer)
        swap(insertyouranswer[dep],insertyouranswer[idx])
    end
  end  
}

 
 
タイトル3:1回の購入と1回の販売が可能であれば、購入は前にしなければならない.最大収益を求める.
 
解答3:欲張りアルゴリズム
 

      ，    i        ，          i         。

public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0)
        return 0;
    int soFarMin = prices[0];
    int maxProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        soFarMin = Math.min(soFarMin, prices[i]);
        maxProfit = Math.max(maxProfit, prices[i] - soFarMin);
    }
    return maxProfit;
}