# -*- coding: utf-8 -*-
# Python Version: Python 3.5.2
# Author: Aman Srivastava
# Date: Oct 4, 2016
# Email: Aman.Srivastava@asu.edu

import numpy as np

#STOCK_PRICES  = [100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]

                                                    # Input Array for Computing Maximum SubArray
STOCK_PRICE_CHANGES = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]

                                                    # 1st Input Matrix for Matrix Multiplication
A=np.array([[ 1, 2, 3, 4,5,6,7,8],                     
         [ 5, 6, 7, 8,5,6,7,8],
         [ 9,10,11,12,5,6,7,8],
         [13,14,15,16,5,6,7,8],
         [ 1, 2, 3, 4,5,6,7,8],
         [ 5, 6, 7, 8,5,6,7,8],
         [ 9,10,11,12,5,6,7,8],
         [13,14,15,16,5,6,7,8]],int)
                                                    # 2nd Input Matrix for Matrix Multiplication
B=np.array([[1,0,0,0,0,0,0,0],                         
         [0,1,0,0,0,0,0,0],
         [0,0,1,0,0,0,0,0],
         [0,0,0,1,0,0,0,0],
         [0,0,0,0,1,0,0,0],
         [0,0,0,0,0,1,0,0],
         [0,0,0,0,0,0,1,0],
         [0,0,0,0,0,0,0,1]],int)

####################################################################################################################
###                                     Maximum SubArray Using Brute Force                                       ###
####################################################################################################################

def find_maximum_subarray_brute(A, low=0, high=-1):
    """
    Returns a tuple (i,j) where A[i:j] is the maximum subarray.
    Implements a brute force approach with time complexity = O(n^2)
    """
    maxSum=0                                        # Keep track of Maximum subArray
    for i in range(low,high+1):                     # Increase Start Index of subArrays
        Sum=0                                       # Compute sum of current subArray
        j=i                                         # Last element of subArrays
        while (j<high+1):                           # Loop till Last element = ArrayLength
            Sum+=A[j]                               # Compute current Sum by adding last element to previous sum  
            j+=1                                    # Increment last element index
            #print('[',sum,']',end='')              # Print sum for all subarrays starting at 'i'
            if(Sum>maxSum):                         # If current sum is greater than Maximum Sum
                maxSum=Sum                          # Replace Maximum Sum with Current Sum
                maxStart=i                          # Store Start Index of MaxSubArray
                maxEnd=j                            # Store End Index of MaxSubArray
    return (maxStart,maxEnd)                        # Return a tuple with Start and End index of MaxSubArray

####################################################################################################################
###                                         Maximum Crossing SubArray                                            ###
####################################################################################################################

def find_maximum_crossing_subarray(A, low, mid,  high):
    """
    Finds the maximum subarray that crosses mid
    Returns a tuple (i,j) where A[i:j] is the maximum subarray.
    """
    maxLeft,maxRight,leftSum,Sum = mid, mid, -1, 0  # Initialize variables
    for i in range(mid,low-1,-1):                   # Loop from mid to low(left)
        Sum+=A[i]                                   # Add sum values
        #print(i,A[i],sum)                          # Print index, value at index, and current sum
        if (Sum>leftSum):                           # If current Sum > Left Sum
            leftSum=Sum                             # Replace LeftSum with Sum
            maxLeft=i                               # Save index i in MaxLeft
    rightSum=-1                                     # Initialize RightSum
    Sum=0                                           # Reset Sum
    for j in range(mid+1,high+1):                   # Loop from mid+1 to high(right)
        Sum+=A[j]                                   # Add sum values
        #print(j,A[j],sum)                          # Print index, value at index, and current sum
        if (Sum>rightSum):                          # If current Sum > Right Sum
            rightSum=Sum                            # Replace RightSum with Sum
            maxRight=j+1                            # Save index j in MaxRight
    return (maxLeft,maxRight,leftSum+rightSum)      # Return tuple with Max Crossing Subarray start, end index and sum

####################################################################################################################
###                                         Maximum SubArray Using Recursion                                     ###
####################################################################################################################

def find_maximum_subarray_recursive(A, low=0, high=-1):
    """
    Returns a tuple (i,j) where A[i:j] is the maximum subarray.
    """
    if (high==low):                                         # If Array contains single element (Base Case)
        return(low,high+1,A[low])                           # Return low and high indices and element at low
    else:                                                   # If high != low
        mid=(low+high)//2                                   # Mid=floor((low+high)/2)
        (leftLow,leftHigh,leftSum)=\
            find_maximum_subarray_recursive(A,low,mid)      # Find max-subarray in the left half
        (rightLow,rightHigh,rightSum)=\
            find_maximum_subarray_recursive(A,mid+1,high)   # Find max-subarray in the right half
        (crossLow,crossHigh,crossSum)=\
            find_maximum_crossing_subarray(A,low,mid,high)  # Find max-subarray in the center
        if (leftSum>=rightSum and leftSum>=crossSum):       # If LeftSum is greatest,
            return (leftLow,leftHigh,leftSum)               # Return leftArray Indices and Sum
        elif (rightSum>=leftSum and rightSum>=crossSum):    # If RightSum is greatest
            return (rightLow,rightHigh,rightSum)            # Return rightArray Indices and Sum
        else:                                               # If Crossing/middle array is greatest
            return (crossLow,crossHigh,crossSum)            # Return Crossing array Indices with Sum

####################################################################################################################
###                                         Maximum SubArray Using Iteration                                     ###
####################################################################################################################

def find_maximum_subarray_iterative(A, low=0, high=-1):
    """
    Returns a tuple (i,j) where A[i:j] is the maximum subarray.
    """
    start,end,localSum,tempStart,bestSum = 0,0,0,low,0      # Initialize variables
    for i in range (low,high+1):                            # Loop i from left to right
        if ((localSum + A[i])> 0):                          # If localSum+A[i] > 0
            localSum+=A[i]                                  # Add A[i] to localSum
        else:                                               # if localSum+A[i] <= 0
            localSum = 0                                    # Set localSum = 0
            tempStart = i+1                                 # Set tempStart = i+1
        if (localSum > bestSum):                            # if localSum > bestSum
            start = tempStart                               # Replace start with tempStart
            end = i+1                                       # Set end = i+1
            bestSum = localSum                              # Set bestSum = localSum
    return (start, end, bestSum)                            # Return MaxSubArray's start and end indices and sum

####################################################################################################################
###                                         Square Matrix Multiplication                                         ###
####################################################################################################################

def square_matrix_multiply(A, B):
    """
    Returns the product AB of matrix multiplication.
    """
    A = np.asarray(A)                                       # Convert to Array (n X m)                                   
    B = np.asarray(B)                                       # Convert to Array (m X p)
    assert A.shape == B.shape , " Invalid Matrices "        # Assert if invalid matrix shape
    assert A.shape == A.T.shape , " Invalid Matrices "      # Assert if invalid matrix shape
    C = np.zeros((A.shape[0],B.shape[1]), dtype=int)        # Zero initialized result matrix
    for i in range(0,A.shape[0]):                           # Loop i from 0 to n
        for j in range(0,B.shape[1]):                       # Loop j from 0 to p
            Sum=0                                           # Reset sum
            for k in range(0,A.shape[1]):                   # Loop k from 0 to m
                Sum+=A[i,k]*B[k,j]                          # Add (new sum+Aik*Bkj) to prev. sum
            C[i,j]=Sum                                      # Set Cij = sum
    return(C)                                               # Return product C

####################################################################################################################
###                                 Matrix Multiplication Using Strassen's Algorithm                             ###
####################################################################################################################

def square_matrix_multiply_strassens(A, B):
    """
    Returns the product AB of matrix multiplication. 
    Assumes len(A) is a power of 2
    """
    A = np.asarray(A)                                       # Convert to Array (n X n)
    B = np.asarray(B)                                       # Convert to Array (n X n)
    assert A.shape == B.shape , " Invalid Matrices "        # Assert if invalid matrix shape
    assert A.shape == A.T.shape , " Invalid Matrices "      # Assert if invalid matrix shape
    assert (len(A)&(len(A) -1))==0,"A is not a power of 2"  # Assert if A is not a power of 2
    n=len(A)                                                # Store Matrix length in n
    if(n==1):                                               # If n=1 (Base Case)
        return np.array([[A[0,0]*B[0,0]]])                  # Return simple multiplication of 1st elements
    C = np.zeros((n,n), dtype=int)                          # Create Zero initialized resultant matrix C
                                                            # STEP 1
    A_11 = A[0:n//2,0:n//2]                                 # Top-Left quarter of A
    A_12 = A[0:n//2,(n//2):n]                               # Top-Right quarter of A
    A_21 = A[(n//2):n,0:n//2]                               # Bottom-Left quarter of A
    A_22 = A[(n//2):n,(n//2):n]                             # Bottom-Right quarter of A

    B_11 = B[0:n//2,0:n//2]                                 # Top-Left quarter of B
    B_12 = B[0:n//2,(n//2):n]                               # Top-Right quarter of B
    B_21 = B[(n//2):n,0:n//2]                               # Bottom-Left quarter of B
    B_22 = B[(n//2):n,(n//2):n]                             # Bottom-Right quarter of B
                                                            # STEP-2 
    S_1 = B_12 - B_22                                       # Compute S1
    S_2 = A_11 + A_12                                       # Compute S2
    S_3 = A_21 + A_22                                       # Compute S3
    S_4 = B_21 - B_11                                       # Compute S4
    S_5 = A_11 + A_22                                       # Compute S5
    S_6 = B_11 + B_22                                       # Compute S6
    S_7 = A_12 - A_22                                       # Compute S7
    S_8 = B_21 + B_22                                       # Compute S8
    S_9 = A_11 - A_21                                       # Compute S9
    S_10= B_11 + B_12                                       # Compute S10
                                                            # STEP 3
    P_1 = square_matrix_multiply_strassens(A_11,S_1)        # Compute P1
    P_2 = square_matrix_multiply_strassens(S_2,B_22)        # Compute P2
    P_3 = square_matrix_multiply_strassens(S_3,B_11)        # Compute P3
    P_4 = square_matrix_multiply_strassens(A_22,S_4)        # Compute P4
    P_5 = square_matrix_multiply_strassens(S_5,S_6)         # Compute P5
    P_6 = square_matrix_multiply_strassens(S_7,S_8)         # Compute P6
    P_7 = square_matrix_multiply_strassens(S_9,S_10)        # Compute P7
                                                            # STEP 4
    C_11= P_5 + P_4 - P_2 + P_6                             # Compute C11
    C_12= P_1 + P_2                                         # Compute C12
    C_21= P_3 + P_4                                         # Compute C21
    C_22= P_5 + P_1 - P_3 - P_7                             # Compute C22
 
    C=np.concatenate((np.concatenate((C_11,C_12),axis=1)\
        ,np.concatenate((C_21,C_22),axis=1)),axis=0)        # Concatenate C11, C12, C21, C22 to form C
    return C                                                # Return C

####################################################################################################################
###                                      Method for Testing All Algorithms                                       ###
####################################################################################################################

def test():
    print("MAX_SUB_ARRAY BRUTE    ",(find_maximum_subarray_brute(STOCK_PRICE_CHANGES,0,len(STOCK_PRICE_CHANGES)-1))[0:2])
    print("MAX_SUB_ARRAY RECURSIVE",(find_maximum_subarray_recursive(STOCK_PRICE_CHANGES,0,len(STOCK_PRICE_CHANGES)-1))[0:2])
    print("MAX_SUB_ARRAY ITERATIVE",(find_maximum_subarray_iterative(STOCK_PRICE_CHANGES,0,len(STOCK_PRICE_CHANGES)-1))[0:2])
    print("\nSQUARE_MATRIX_MULTIPLY\n",square_matrix_multiply(A,B));
    print("\nSQUARE_MATRIX_MULTIPLY STRASSEN'S\n",square_matrix_multiply_strassens(A,B));

####################################################################################################################
###                                                 Main Method                                                  ###
####################################################################################################################

if __name__ == '__main__':
    test()

##################################################祖阿曼 斯里瓦斯塔瓦##################################################
