02/19: SP Workflow 3

 

1. if site authentication provider type is form based , user might not see “open with windows explorer” in actions menu of document.

2.

Create SP workflow in the follwoing ways:

 

• Create workflow in SP Designer with limited functionality
  • The  created workflow can only associated a single list or library but not apply to the whole site
• Create workflow programmatically in VS and deploy to server(GAC or local bin folder).

 

 

An interview Question (ZT)

http://www.cnblogs.com/grenet/archive/2010/02/21/1670208.html

 

“一道算法题，看看大家的思路”，看了众多的回复，本人愚钝，没有看明白其中的奥妙。在细细研究《编程之美》中的文章后，终于理解了这个算法的思路。现将这个算法的演算过程以及代码实现（VB2005）赋予其后，和各位交流。

现再将题目复述一遍：

题目描述：有31，-41，59，26，-53，58，97，-93，-23，84十个数。SUM（N，M）表示从第N个数到到第M个数的和。例如：SUM（2，3）=-41+59=18。问：最大的和是多少？对应的N和M是多少？

先不管N和M的计算，直接计算SUM，看看用什么算法。

算法一：直接遍历穷举，求出SUM。代码如下：

Public Function MaxSum1() As Integer
        Dim i As Integer, j As Integer, k As Integer,  _
　　　　　　　　Sum As Integer, Maximum As Integer = Integer.MinValue

        For i = 0 To A.GetUpperBound(0)
            For j = i To A.GetUpperBound(0)
                Sum = 0
                For k = i To j
                    Sum += A(k)
                    If Sum > Maximum Then Maximum = Sum
                Next
            Next
        Next
        Return Maximum
    End Function

这个代码最容易理解，但是效率最低，算法的复杂度为O(N³)

算法二，在算法一的基础上改进，因为SUM（N，M）=SUM（N，M-1）+A（M），基于这个原理，将上述代码中的最里面的一层循环去掉。

Public Function MaxSum2() As Integer
        Dim i As Integer, j As Integer, Sum As Integer, _
　　　　　　　　　　 Maximum As Integer = Integer.MinValue
        For i = 0 To A.GetUpperBound(0)
            Sum = 0
            For j = i To A.GetUpperBound(0)
                Sum += A(j)
                If Sum > Maximum Then Maximum = Sum
            Next
        Next
        Return Maximum
End Function

这个代码也很容易理解，算法执行效率有明显的提高，算法的复杂度为O(N²)，但还不够。

算法三：

考虑数组第一个元素A（0）和最大和的一段数组A（N），……，A（M）。他们之间有如下关系：

1、当0=N=M时，元素A（0）本身构成最大和的一段

2、当0=N<M时，最大和的一段以A（0）开始

3、当0<N时，A（0）和最大和一段没有什么关系。

假设数组有N个元素，分别为A（0），A（1），……，A（N-1）

并且我还知道从A（1）到A（N-1）的最大和为All（1），从A（1）到A（N-1）中包含A（1）的最大和为Start（1）

那么，从A（0）到A（N-1）的最大和All（0）就一定有下面的关系式：

All（0）=Max｛A（0），A（0）+Start（1），All（1）｝

而Start（0）有如下的关系式：

Start（0）=Max｛A（0），A（0）+Start（1）｝

看了上面的分析，将N个元素的问题就转化为了N-1个元素的问题。这是我想到了递推。（书上以及很多其他的博客说是动态规划，我没有理解，个人比较愚钝）

将上面的式子整理一下，建立好递推关系：

Start（i）=Max｛A（i），A（i）+Start（i+1）｝

All（i）=Max｛Start（i），All（i+1）｝

The goal is to get All (N-1)

Note : result need to be continuous

代码如下：

　　Public Function Max(ByVal X As Integer, ByVal Y As Integer) As Integer
        Return IIf(X > Y, X, Y)
    End Function

    Public Function MaxSum3() As Integer
        Dim i As Integer, Start() As Integer, All() As Integer
        ReDim Start(A.GetUpperBound(0))
        ReDim All(A.GetUpperBound(0))

        Start(A.GetUpperBound(0)) = A(A.GetUpperBound(0))
        All(A.GetUpperBound(0)) = A(A.GetUpperBound(0))

        For i = A.GetUpperBound(0) - 1 To 0 Step -1
            Start(i) = Max(A(i), A(i) + Start(i + 1))
            All(i) = Max(Start(i), All(i + 1))
        Next

        Return All(0)
    End Function

这个算法的效率很高，算法复杂度为O(N)，但是引用了两个数组。仔细观察两个数组的使用情况，发现其实只要使用两个变量就完全可以了，下面是改进的代码。

　　Public Function Max(ByVal X As Integer, ByVal Y As Integer) As Integer
        Return IIf(X > Y, X, Y)
    End Function

    Public Function MaxSum4() As Integer
        Dim i As Integer, Start As Integer, All As Integer
        Start = A(A.GetUpperBound(0))
        All = A(A.GetUpperBound(0))
        For i = A.GetUpperBound(0) - 1 To 0 Step -1
            Start = Max(A(i), A(i) + Start)
            All = Max(Start, All)
        Next
        Return All
    End Function

将上面的代码，仔细分析一下可以发现：

Start=Max（A（i），A（i）+Start）

可以改写为：

If Start<0 Then

Start=A（i）

Else

Start=A（i）+Start

End If

继而可以改写为

If Start<0 Then Start=0

Start=A（i）+Start

而All = Max(Start, All)可以改写为

If Start>All Then All=Start

故上面的代码，可以改写为一个函数，减少系统的开销

 Public Function MaxSum5() As Integer
        Dim i As Integer, Start As Integer, All As Integer
        Start = A(A.GetUpperBound(0))
        All = A(A.GetUpperBound(0))

        For i = A.GetUpperBound(0) - 1 To 0 Step -1
            If Start < 0 Then Start = 0
            Start += A(i)

            If Start > All Then All = Start
        Next
        Return All
    End Function

至此，代码效率高，又简洁明了。唯一的缺憾是从数组的最后一个倒推，下面的代码改成正推

Public Function MaxSum6() As Integer
        Dim i As Integer, Start As Integer, All As Integer
        Start = A(0)
        All = A(0)

        For i = 1 To A.GetUpperBound(0)
            If Start < 0 Then Start = 0
            Start += A(i)

            If Start > All Then All = Start
        Next

        Return All
    End Function